Defective chromatic polynomials
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866918486956048384 |
|---|---|
| author | Asgarli, Shamil McGinley, Tamsen Whitehead Xue, Nicholas |
| author_facet | Asgarli, Shamil McGinley, Tamsen Whitehead Xue, Nicholas |
| contents | For a graph $G$ and an integer $d\geq 0$, the defective chromatic polynomial $χ_d(G;k)$ counts the $k$-colorings of $G$ in which each vertex has at most $d$ neighbors of its own color. We investigate which structural properties of $G$ are determined by the full family $\{χ_d(G;k)\}_{d\geq 0}$. We establish a contraction formula expressing $χ_d(G;k)$ as a sum of ordinary chromatic polynomials of the edge contractions of $G$. As a first application, we prove that for triangle-free graphs, the full family determines the degree sequence. For trees, we show further that the family $\{χ_d(T;k)\}_{d\geq 0}$ determines the path-subgraph counts $N(P_j,T)$ for $j=1,2,3,4$, but not for $j=5$. For each $n\geq 9$, we construct a pair of nonisomorphic trees of order $n$ that share the same defective chromatic polynomials for every $d\geq 0$. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2605_05550 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | Defective chromatic polynomials Asgarli, Shamil McGinley, Tamsen Whitehead Xue, Nicholas Combinatorics Primary: 05C15, 05C31, Secondary: 05C05, 05C60 For a graph $G$ and an integer $d\geq 0$, the defective chromatic polynomial $χ_d(G;k)$ counts the $k$-colorings of $G$ in which each vertex has at most $d$ neighbors of its own color. We investigate which structural properties of $G$ are determined by the full family $\{χ_d(G;k)\}_{d\geq 0}$. We establish a contraction formula expressing $χ_d(G;k)$ as a sum of ordinary chromatic polynomials of the edge contractions of $G$. As a first application, we prove that for triangle-free graphs, the full family determines the degree sequence. For trees, we show further that the family $\{χ_d(T;k)\}_{d\geq 0}$ determines the path-subgraph counts $N(P_j,T)$ for $j=1,2,3,4$, but not for $j=5$. For each $n\geq 9$, we construct a pair of nonisomorphic trees of order $n$ that share the same defective chromatic polynomials for every $d\geq 0$. |
| title | Defective chromatic polynomials |
| topic | Combinatorics Primary: 05C15, 05C31, Secondary: 05C05, 05C60 |
| url | https://arxiv.org/abs/2605.05550 |