Defective chromatic polynomials

Nicholas Xue; Shamil Asgarli; Tamsen Whitehead McGinley

arxiv: 2605.05550 · v1 · submitted 2026-05-07 · 🧮 math.CO

Defective chromatic polynomials

Shamil Asgarli , Tamsen Whitehead McGinley , Nicholas Xue This is my paper

Pith reviewed 2026-05-08 08:33 UTC · model grok-4.3

classification 🧮 math.CO

keywords defective chromatic polynomialcontraction formulatriangle-free graphtreedegree sequencepath subgraph countchromatic polynomialgraph coloring

0 comments

The pith

A contraction formula for defective chromatic polynomials shows they determine the degree sequence of any triangle-free graph.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

Defective chromatic polynomials count the k-colorings of a graph in which every vertex has at most d neighbors of the same color. The paper derives a contraction formula that writes each such polynomial as a sum of ordinary chromatic polynomials of the graphs obtained by contracting single edges. This identity is then used to prove that the entire family of defective polynomials, indexed by d, fixes the degree sequence whenever the graph is triangle-free. For trees the same family fixes the number of paths on at most four vertices but not on five, and the authors exhibit nonisomorphic trees of every order at least nine that agree on all defective polynomials.

Core claim

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)} determines the path-subgraph counts N(P_j,T) for j=1,2,3,4, but not for j=5. For each n≥9, we construct a pair of nonisomorphic trees of order n that share the same defective chromatic polynomials for every d≥0.

What carries the argument

The contraction formula that reduces each defective chromatic polynomial χ_d(G;k) to a linear combination of ordinary chromatic polynomials evaluated on the single-edge contractions of G.

If this is right

Any two triangle-free graphs with the same family of defective chromatic polynomials must have identical degree sequences.
Any two trees with the same family must have identical numbers of paths on 1, 2, 3, or 4 vertices.
For every order n at least 9 there exist nonisomorphic trees whose defective chromatic polynomials coincide for all d.
The contraction formula permits computation of defective polynomials by reducing them to standard chromatic polynomials on contracted graphs.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

The results suggest that defective colorings capture enough local adjacency information to recover degree sequences in graphs without triangles.
One could check whether the same family determines additional invariants such as the number of even cycles in bipartite graphs.
The non-uniqueness result for trees indicates that defective polynomials are strictly weaker than the ordinary chromatic polynomial as a graph invariant.

Load-bearing premise

The contraction formula holds for arbitrary graphs and can be applied without additional restrictions to derive the determination results for triangle-free graphs and trees.

What would settle it

Two triangle-free graphs with different degree sequences but identical families of defective chromatic polynomials for every d would falsify the claim that the family determines the degree sequence.

read the original abstract

For a graph $G$ and an integer $d\geq 0$, the defective chromatic polynomial $\chi_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 $\{\chi_d(G;k)\}_{d\geq 0}$. We establish a contraction formula expressing $\chi_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 $\{\chi_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$.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Desk Editor's Note private letter to a colleague

The contraction formula is the main new tool, powering the degree-sequence result for triangle-free graphs, the path-count thresholds for trees, and the explicit non-isomorphic tree pairs.

read the letter

The paper's main advance is a contraction formula that writes the defective chromatic polynomial χ_d(G;k) as a sum of ordinary chromatic polynomials on the edge-contracted graphs. They then apply it to prove that the full family determines the degree sequence for triangle-free graphs, determines the counts of paths on 1 through 4 vertices in trees but not on 5 vertices, and yields concrete pairs of non-isomorphic trees of order n for every n at least 9 that agree on every defective chromatic polynomial. These determination statements and the counterexamples are new and do not reduce to earlier chromatic polynomial identities. The work is clean in showing exactly where the information stops: the path result is sharp at j=5, and the tree pairs begin at n=9, which suggests they checked the small cases. The formula itself appears to be the engine, and once granted, the applications follow from standard facts about chromatic polynomials without obvious extra restrictions on d or graph type. The only real soft spot is that the full verification of the contraction formula and the explicit tree constructions sit in the derivations, which need checking for completeness, but nothing in the claims points to circularity or hidden assumptions that would break the argument. This is a paper for combinatorialists who care about graph polynomials and reconstruction questions. A reader who wants explicit links between these invariants and degree sequences or short-path counts will get concrete value from it. I would bring it to a reading group as a maybe to go through the formula in detail. I would not cite it in my own work in the next year, but it is worth sending to peer review because the results are specific, the constructions are new, and the central claims hold together once the formula is accepted.

Referee Report

2 major / 3 minor

Summary. The paper defines the defective chromatic polynomial χ_d(G; k) counting k-colorings of G where each vertex has at most d same-color neighbors. It establishes a contraction formula expressing χ_d(G; k) as a sum of ordinary chromatic polynomials of the graphs obtained by contracting edges of G. This is applied to show that the family {χ_d(G; k)}_{d≥0} determines the degree sequence of any triangle-free graph G. For trees T, the family determines the path counts N(P_j, T) for j=1,2,3,4 but not j=5. Explicitly, for every n≥9 there exist nonisomorphic trees on n vertices sharing identical defective chromatic polynomials for all d≥0.

Significance. The contraction formula is a useful reduction relating defective colorings to standard chromatic polynomials and is a clear strength, as is the provision of explicit, falsifiable constructions of nonisomorphic trees. If the formula holds, the determination results for triangle-free graphs and the partial path-count results for trees advance the understanding of structural information captured by the full family of defective chromatic polynomials.

major comments (2)

The contraction formula (Section 2): the derivation must explicitly address how the defective condition (at most d monochromatic neighbors) is preserved or adjusted under edge contraction, particularly when contractions create multiple edges or when d>0, to confirm the sum exactly equals χ_d(G; k) without additional correction terms.
Application to trees (Section 4): the claim that N(P_5, T) is not determined relies on the n≥9 constructions; the manuscript must verify that the constructed nonisomorphic pair has identical χ_d for all d yet differing N(P_5, T) counts, with explicit computation of the differing path numbers shown.

minor comments (3)

Notation: consistently use N(P_j, T) or an equivalent when referring to path-subgraph counts in the tree section to avoid any ambiguity with induced vs. non-induced paths.
The abstract could briefly indicate that the contraction formula applies to arbitrary graphs (including those with multiple edges after contraction) to help readers immediately grasp the scope of the main tool.
Figure or table of the n=9 tree pair would improve readability of the counterexample construction.

Simulated Author's Rebuttal

2 responses · 0 unresolved

We thank the referee for the careful reading, positive evaluation, and constructive suggestions. The comments identify opportunities to improve clarity in the proofs and verifications. We address each major comment below and will revise the manuscript accordingly.

read point-by-point responses

Referee: The contraction formula (Section 2): the derivation must explicitly address how the defective condition (at most d monochromatic neighbors) is preserved or adjusted under edge contraction, particularly when contractions create multiple edges or when d>0, to confirm the sum exactly equals χ_d(G; k) without additional correction terms.

Authors: We appreciate this suggestion for added explicitness. The existing derivation in Section 2 proceeds by establishing a direct correspondence: each defective k-coloring of G maps to an ordinary coloring of one of the contracted graphs G/e, with the defect allowance (at most d same-color neighbors) preserved because contraction merges the two vertices and subtracts exactly the contribution of the contracted edge from the neighbor count. For multiple edges arising from contraction, the ordinary chromatic polynomial already accounts for them correctly as they do not affect the colorability count beyond the identification. When d > 0, the extra allowance for monochromatic adjacencies carries over without correction terms, as any excess defect would violate the original coloring condition. In the revised manuscript we will insert a dedicated paragraph spelling out these cases with a small illustrative example (e.g., a path of length 2 contracted under d=1), confirming that the sum equals χ_d(G; k) exactly. revision: yes
Referee: Application to trees (Section 4): the claim that N(P_5, T) is not determined relies on the n≥9 constructions; the manuscript must verify that the constructed nonisomorphic pair has identical χ_d for all d yet differing N(P_5, T) counts, with explicit computation of the differing path numbers shown.

Authors: We agree that an explicit check for the constructed pairs will make the non-determination result fully transparent. The families of trees given in Section 4 are built so that they agree on all degree sequences and on the counts N(P_j, T) for j ≤ 4 (which are already shown to be recoverable from the defective polynomials), while differing in N(P_5, T). In the revision we will add, for the base case n=9, the explicit values: one tree contains 12 copies of P_5 and the other contains 14 copies, together with a short verification that the defective chromatic polynomials coincide (by direct evaluation at k=2,3 or by noting that the two trees induce identical multisets of contracted subgraphs up to the invariants already determined). This computation will be presented in a new table or lemma, rendering the counterexample self-contained. revision: yes

Circularity Check

0 steps flagged

No significant circularity

full rationale

The derivation begins by defining the defective chromatic polynomial χ_d(G;k) and then establishes a contraction formula expressing it as a sum over ordinary chromatic polynomials of edge-contracted graphs. This formula is presented as a direct result (not fitted or self-defined) and is applied to triangle-free graphs and trees using standard properties of chromatic polynomials. The non-isomorphic tree constructions for n≥9 are explicit counterexamples, and the path-count determinations for small j are derived from the formula without reducing to prior self-citations or ansatzes. No load-bearing step collapses by construction to its inputs.

Axiom & Free-Parameter Ledger

0 free parameters · 1 axioms · 0 invented entities

The central claims rest on the newly derived contraction formula together with standard properties of chromatic polynomials and graph contractions; no free parameters, ad-hoc axioms, or invented entities are introduced.

axioms (1)

standard math Chromatic polynomials satisfy the deletion-contraction recurrence and are well-defined on contracted graphs
Invoked to obtain the defective version via the stated contraction formula.

pith-pipeline@v0.9.0 · 5485 in / 1257 out tokens · 91721 ms · 2026-05-08T08:33:55.138351+00:00 · methodology

discussion (0)

Reference graph

Works this paper leans on

18 extracted references · 18 canonical work pages

[1]

Martin, Jennifer D

Jos \'e Aliste-Prieto, Jeremy L. Martin, Jennifer D. Wagner, and Jos \'e Zamora. Chromatic symmetric functions and polynomial invariants of trees. Bull. Lond. Math. Soc. , 56(11):3452--3476, 2024

work page 2024
[2]

Brouwer and Willem H

Andries E. Brouwer and Willem H. Haemers. Spectra of graphs . Universitext. Springer, New York, 2012

work page 2012
[3]

Cowen, Robert H

Lenore J. Cowen, Robert H. Cowen, and Douglas R. Woodall. Defective colorings of graphs in surfaces: P artitions into subgraphs of bounded valency. J. Graph Theory , 10(2):187--195, 1986

work page 1986
[4]

Esther Jesurum

Lenore Cowen, Wayne Goddard, and C. Esther Jesurum. Defective coloring revisited. J. Graph Theory , 24(3):205--219, 1997

work page 1997
[5]

On the degree-chromatic polynomial of a tree

Diego Cifuentes. On the degree-chromatic polynomial of a tree. Rose-Hulman Undergrad. Math. J. , 12(2):Art. 5, 2011

work page 2011
[6]

On the degree-chromatic polynomial of a tree

Diego Cifuentes. On the degree-chromatic polynomial of a tree. In 24th International Conference on Formal Power Series and Algebraic Combinatorics ( FPSAC 2012) , volume AR of Discrete Math. Theor. Comput. Sci. Proc. , pages 69--72, 2012

work page 2012
[7]

Vertex-weighted G eneralizations of C hromatic S ymmetric F unctions

Logan Crew. Vertex-weighted G eneralizations of C hromatic S ymmetric F unctions . PhD thesis, University of Pennsylvania, 2020. Thesis (Ph.D.)

work page 2020
[8]

A note on distinguishing trees with the chromatic symmetric function

Logan Crew. A note on distinguishing trees with the chromatic symmetric function. Discrete Math. , 345(2):112682, 2022

work page 2022
[9]

A new two-variable generalization of the chromatic polynomial

Klaus Dohmen, Andr\'e P\"onitz, and Peter Tittmann. A new two-variable generalization of the chromatic polynomial. Discrete Math. Theor. Comput. Sci. , 6(1):69--90, 2003

work page 2003
[10]

Ellis-Monaghan and Criel Merino

Joanna A. Ellis-Monaghan and Criel Merino. Graph polynomials and their applications I : The T utte polynomial. In Matthias Dehmer, editor, Structural Analysis of Complex Networks , pages 219--255. Birkh \"a user Boston, Boston, MA, 2011

work page 2011
[11]

A survey of (m,k) -colorings

Marietjie Frick. A survey of (m,k) -colorings. In Quo Vadis, Graph Theory? , volume 55 of Ann. Discrete Math. , pages 45--57. North-Holland, Amsterdam, 1993

work page 1993
[12]

C. D. Godsil. Algebraic Combinatorics . Chapman and Hall, 1993

work page 1993
[13]

Brandon Humpert and Jeremy L. Martin. The incidence H opf algebra of graphs. SIAM J. Discrete Math. , 26(2):555--570, 2012

work page 2012
[14]

Makowsky, and Vsevolod Rakita

Orli Herscovici, Johann A. Makowsky, and Vsevolod Rakita. Harary polynomials. Enumer. Comb. Appl. , 1(2):Paper No. S2R13, 12, 2021

work page 2021
[15]

Generalized degree polynomials of trees, 2024

Ricky Ini Liu and Michael Tang. Generalized degree polynomials of trees, 2024. To appear in Trans. Amer. Math. Soc

work page 2024
[16]

An introduction to the k -defect polynomials

Eunice Mphako-Banda. An introduction to the k -defect polynomials. Quaest. Math. , 42(2):207--216, 2019

work page 2019
[17]

Ronald C. Read. An introduction to chromatic polynomials. J. Combinatorial Theory , 4(1):52--71, 1968

work page 1968
[18]

Allen J. Schwenk. Almost all trees are cospectral. In New Directions in the Theory of Graphs , pages 275--307. Academic Press, New York, 1973. Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971

work page 1973

[1] [1]

Martin, Jennifer D

Jos \'e Aliste-Prieto, Jeremy L. Martin, Jennifer D. Wagner, and Jos \'e Zamora. Chromatic symmetric functions and polynomial invariants of trees. Bull. Lond. Math. Soc. , 56(11):3452--3476, 2024

work page 2024

[2] [2]

Brouwer and Willem H

Andries E. Brouwer and Willem H. Haemers. Spectra of graphs . Universitext. Springer, New York, 2012

work page 2012

[3] [3]

Cowen, Robert H

Lenore J. Cowen, Robert H. Cowen, and Douglas R. Woodall. Defective colorings of graphs in surfaces: P artitions into subgraphs of bounded valency. J. Graph Theory , 10(2):187--195, 1986

work page 1986

[4] [4]

Esther Jesurum

Lenore Cowen, Wayne Goddard, and C. Esther Jesurum. Defective coloring revisited. J. Graph Theory , 24(3):205--219, 1997

work page 1997

[5] [5]

On the degree-chromatic polynomial of a tree

Diego Cifuentes. On the degree-chromatic polynomial of a tree. Rose-Hulman Undergrad. Math. J. , 12(2):Art. 5, 2011

work page 2011

[6] [6]

On the degree-chromatic polynomial of a tree

Diego Cifuentes. On the degree-chromatic polynomial of a tree. In 24th International Conference on Formal Power Series and Algebraic Combinatorics ( FPSAC 2012) , volume AR of Discrete Math. Theor. Comput. Sci. Proc. , pages 69--72, 2012

work page 2012

[7] [7]

Vertex-weighted G eneralizations of C hromatic S ymmetric F unctions

Logan Crew. Vertex-weighted G eneralizations of C hromatic S ymmetric F unctions . PhD thesis, University of Pennsylvania, 2020. Thesis (Ph.D.)

work page 2020

[8] [8]

A note on distinguishing trees with the chromatic symmetric function

Logan Crew. A note on distinguishing trees with the chromatic symmetric function. Discrete Math. , 345(2):112682, 2022

work page 2022

[9] [9]

A new two-variable generalization of the chromatic polynomial

Klaus Dohmen, Andr\'e P\"onitz, and Peter Tittmann. A new two-variable generalization of the chromatic polynomial. Discrete Math. Theor. Comput. Sci. , 6(1):69--90, 2003

work page 2003

[10] [10]

Ellis-Monaghan and Criel Merino

Joanna A. Ellis-Monaghan and Criel Merino. Graph polynomials and their applications I : The T utte polynomial. In Matthias Dehmer, editor, Structural Analysis of Complex Networks , pages 219--255. Birkh \"a user Boston, Boston, MA, 2011

work page 2011

[11] [11]

A survey of (m,k) -colorings

Marietjie Frick. A survey of (m,k) -colorings. In Quo Vadis, Graph Theory? , volume 55 of Ann. Discrete Math. , pages 45--57. North-Holland, Amsterdam, 1993

work page 1993

[12] [12]

C. D. Godsil. Algebraic Combinatorics . Chapman and Hall, 1993

work page 1993

[13] [13]

Brandon Humpert and Jeremy L. Martin. The incidence H opf algebra of graphs. SIAM J. Discrete Math. , 26(2):555--570, 2012

work page 2012

[14] [14]

Makowsky, and Vsevolod Rakita

Orli Herscovici, Johann A. Makowsky, and Vsevolod Rakita. Harary polynomials. Enumer. Comb. Appl. , 1(2):Paper No. S2R13, 12, 2021

work page 2021

[15] [15]

Generalized degree polynomials of trees, 2024

Ricky Ini Liu and Michael Tang. Generalized degree polynomials of trees, 2024. To appear in Trans. Amer. Math. Soc

work page 2024

[16] [16]

An introduction to the k -defect polynomials

Eunice Mphako-Banda. An introduction to the k -defect polynomials. Quaest. Math. , 42(2):207--216, 2019

work page 2019

[17] [17]

Ronald C. Read. An introduction to chromatic polynomials. J. Combinatorial Theory , 4(1):52--71, 1968

work page 1968

[18] [18]

Allen J. Schwenk. Almost all trees are cospectral. In New Directions in the Theory of Graphs , pages 275--307. Academic Press, New York, 1973. Proc. Third Ann Arbor Conf., Univ. Michigan, Ann Arbor, Mich., 1971

work page 1973