Defective chromatic polynomials
Shamil Asgarli, Tamsen Whitehead McGinley, Nicholas Xue · 2026
Read Defective chromatic polynomials by Shamil Asgarli, Tamsen Whitehead McGinley, Nicholas Xue (2026) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2605-05550.txt.
Introduction
A defective coloring lets each vertex share its color with a few neighbors, relaxing the classic coloring rule. Shamil Asgarli, Tamsen Whitehead McGinley, and Nicholas Xue ask how much a graph's structure is fixed by counting such colorings at every defect level. The counts form a family of defective chromatic polynomials.
They prove a contraction formula that writes these counts through ordinary chromatic polynomials. For triangle-free graphs, the family determines the degree sequence. For trees it fixes short path counts but not longer ones, and they build pairs of distinct trees that share every defective polynomial.
Catalog record
| CREATOR | Shamil Asgarli, Tamsen Whitehead McGinley, Nicholas Xue |
|---|---|
| YEAR | 2026 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 38 KB |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2605.05550
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Defective chromatic polynomials Shamil Asgarli, Tamsen Whitehead McGinley, Nicholas Xue Abstract . For a graph G G and an integer d ≥ 0 d\geq 0 , the defective chromatic polynomial χ d ( G , k ) \chi_{d}(G;k) counts the k k -colorings of G G in which each vertex has at most d d neighbors of its own color. We investigate which structural properties of G G are determined by the full family { χ d ( G , k ) } d ≥ 0 \{\chi_{d}(G;k)\}_{d\geq 0} . We establish a contraction formula expressing χ d ( G , k ) \chi_{d}(G;k) as a sum of ordinary chromatic polynomials of the edge contractions of G 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 ≥ 0 \{\chi_{d}(T;k)\}_{d\geq 0} determines the path-subgraph counts N ( P j , T ) N(P_{j},T) for j = 1 , 2 , 3 , 4 j=1,2,3,4 , but not for j = 5 j=5 . For each n ≥ 9 n\geq 9 , we construct a pair of nonisomorphic trees of order n n that share the same defective chromatic polynomials for every d ≥ 0 d\geq 0 . 2020 Mathematics Subject Classification Primary: 05C15, 05C31; Secondary: 05C05, 05C60 1. Introduction Let G be a finite simple graph. A (k,d) -coloring of G is a map c\colon V(G)\to[k]\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\{1,2,\dots,k\} such that every vertex v\in V(G) has at most d neighbors w\in N_{G}(v) with c(w)=c(v) . Equivalently, the color classes induce subgraphs of maximum degree at most d . Definition 1.1 . For a graph G and an integer d\geq 0 , we write \chi_{d}(G;k) for the number of (k,d) -colorings of G and call it the defective chromatic polynomial of G . Two extreme cases are immediate: setting d=0 recovers the ordinary chromatic polynomial \chi_{0}(G;k)=\chi(G;k) , while setting d\geq\Delta(G) imposes no restriction, yielding \chi_{d}(G;k)=k^{|V(G)|} . The intermediate range, where the new phenomena arise, is 1\leq d\leq\Delta(G)-1 . The name degree chromatic polynomial also appears in the literature, under a slightly different indexing convention. This terminology is due to Humpert and Martin [ HM12 ] , who introduced the polynomial as part of a Hopf-algebraic framework. A conjecture of Humpert and Martin on the leading terms for trees was later proved by Cifuentes [ Cif11 , Cif12 ] . In their notation, P_{m}(G,k) counts the k -colorings in which every vertex has fewer than m neighbors of its own color. The two definitions are related by \chi_{d}(G;k)=P_{d+1}(G,k) . Either way, the abbreviation DCP is consistent with both names. Defective colorings belong to the broader theory of improper colorings and (m,k) -colorings; see Cowen, Cowen, and Woodall [ CCW86 ] , Frick [ Fri93 ] , and Cowen, Goddard, and Jesurum [ CGJ97 ] . The defective chromatic polynomial is a special case of the Harary polynomial of Herscovici, Makowsky, and Rakita [ HMR21 ] . For background on chromatic polynomials, see Read [ Rea68 ] . The defective chromatic polynomial should be distinguished from the q -defect polynomial , which counts colorings with exactly q monochromatic edges. That invariant was studied by Mphako-Banda [ MB19 ] ; for a broader discussion of related graph polynomials, see Ellis-Monaghan and Merino [ EMM11 ] . Both invariants measure how far a coloring is from being proper: the q -defect polynomial counts the total number of monochromatic edges, while \chi_{d}(G;k) bounds the monochromatic degree at each vertex. The ordinary chromatic polynomial is well known to be an incomplete invariant of graphs, and even of trees. Allowing a defect parameter produces a family of invariants, and it is natural to ask what additional information this family carries: Question 1.2 . Which properties of a graph G are determined by the full family \{\chi_{d}(G;k):d\geq 0\} of its defective chromatic polynomials? Our first result is that for triangle-free graphs, the full defective family determines the degree sequence. Theorem 1.3 . Let G be a triangle-free graph. Then the full family \{\chi_{d}(G;k):d\geq 0\} determines the degree sequence of G . For trees, we prove more: the defective polynomials determine the counts of short paths. Let N(H,G) denote the number of subgraphs of G isomorphic to H . Theorem 1.4 . Let T_{1} and T_{2} be two trees with \chi_{d}(T_{1};k)=\chi_{d}(T_{2};k) for every d\geq 0 . Then N(P_{j},T_{1})=N(P_{j},T_{2})\qquad\text{for each }j\in\{1,2,3,4\}. On the other hand, we exhibit such trees for which N(P_{5},T_{1})\neq N(P_{5},T_{2}) , showing that Theorem 1.4 is sharp. In particular, the full defective family is not a complete invariant, even for trees; in fact, infinitely many pairs of trees witness this failure. Theorem 1.5 . There exist infinitely many pairs of nonisomorphic trees having the same full family of defective chromatic polynomials. In the final section, we show that the DCP family is incomparable with both the two-variable polynomial of Dohmen, Pönitz, and Tittmann [ DPT03 ] and the generalized degree polynomial of Crew [ Cre20 ] . Organization. Section 2 establishes a formula for \chi_{d}(G;k) as a sum of ordinary chromatic polynomials of contracted graphs. Theorems 1.3 and 1.4 are proved in Sections 3 and 4 , respectively. In Section 5 , we prove Theorem 1.5 by constructing an explicit infinite family of trees. Finally, Section 6 compares DCP with several other graph polynomials on trees. 2. A contraction formula Every coloring of G has a naturally associated set of monochromatic edges . If this edge set has maximum degree at most d , the coloring descends to a proper coloring of the graph obtained by contracting these edges. Summing over all such edge sets yields a formula for \chi_{d}(G;k) in terms of ordinary chromatic polynomials. For A\subseteq E(G) , write G[A] for the spanning subgraph of G with edge set A , and G/A for the graph obtained by simultaneously contracting every edge in A . We regard G/A as a multigraph, allowing loops and parallel edges. The chromatic polynomial is defined as usual; in particular, a loop forces it to vanish, while parallel edges have no effect on proper colorings. Theorem 2.1 . Let G be a graph and let d\geq 0 . Then \chi_{d}(G;k)=\sum_{\begin{subarray}{c}A\subseteq E(G)\\ \Delta(G[A])\leq d\end{subarray}}\chi_{0}(G/A;k). Proof. Given a (k,d) -coloring c of G , let A_{c}\mathrel{\mathchoice{\vbox{\hbox{$\displaystyle:$}}}{\vbox{\hbox{$\textstyle:$}}}{\vbox{\hbox{$\scriptstyle:$}}}{\vbox{\hbox{$\scriptscriptstyle:$}}}{=}}\{uv\in E(G):c(u)=c(v)\} be the set of monochromatic edges. Since the number of monochromatic neighbors of a vertex v equals its degree in G[A_{c}] , the defect condition on c is equivalent to \Delta(G[A_{c}])\leq d . Contracting A_{c} , we see that c descends to a coloring of G/A_{c} , since every edge of A_{c} is monochromatic. No loop arises in G/A_{c} : if an edge uv\notin A_{c} had both endpoints in the same connected component of G[A_{c}] , then u and v would share a color, forcing uv\in A_{c} , a contradiction. Hence the induced coloring on G/A_{c} is proper. Conversely, given A\subseteq E(G) with \Delta(G[A])\leq d , each proper coloring of G/A lifts uniquely to a (k,d) -coloring of G with A_{c}=A . The lift assigns each vertex v\in V(G) the color of the vertex of G/A containing v