Skip to content
DraconiticResearch
Search Sources API
203,203 studies31 sourcesUpdated 14 min ago
PreprintCC BY 4.0arXiv

Defective chromatic polynomials

  • Shamil Asgarli
  • Tamsen Whitehead McGinley
  • Nicholas Xue
Open at sourcePDFDOICite

Abstract

For a graph G and an integer d≥ 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≥ 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≥ 0 determines the path-subgraph counts N(Pj,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.

Related

  1. An improved lower bound for the blowup defective chromatic separation constant
    Guillaume Lecomte
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsOptimisation & controlarXiv
  2. Generalized Chromatic Polynomials of Cycles and uni-cyclic Graphs
    Dipnit Biswas, R. Venkatesh
    arXivPreprintCC BY 4.0Full textCombinatorics & discrete mathematicsarXiv
  3. When chromatic polynomials coincide with list-color functions: a threshold linear in the maximum degree
    Meiqiao Zhang, Fengming Dong
    arXivPreprintarXiv licenceFull textCombinatorics & discrete mathematicsarXiv
  4. On the k-Distance Chromatic Number of Unicyclic Graphs
    Rosário Fernandes, Rúben Palma
    Discrete Mathematics LettersPeer-reviewedCC BYFull textGeneral mathematicsDOAJ
  5. Minimal Cayley graphs with large chromatic number
    James Davies, Meike Hatzel, Liana Yepremyan
    arXivPreprintarXiv licenceFull textAlgebra & number theoryCombinatorics & discrete mathematicsarXiv

Cite

BibTeXRIS
BibTeX
@misc{asgarli2026defective,
  title = {{Defective chromatic polynomials}},
  author = {Shamil Asgarli and Tamsen Whitehead McGinley and Nicholas Xue},
  howpublished = {arXiv},
  year = {2026},
  month = sep,
  doi = {10.48550/arxiv.2605.05550},
  eprint = {2605.05550},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/2605.05550},
  note = {CC BY 4.0},
}
RIS
TY  - UNPB
TI  - Defective chromatic polynomials
AU  - Shamil Asgarli
AU  - Tamsen Whitehead McGinley
AU  - Nicholas Xue
PY  - 2026
DA  - 2026/09/28
PB  - arXiv
DO  - 10.48550/arxiv.2605.05550
UR  - https://arxiv.org/abs/2605.05550
AB  - For a graph G and an integer d≥ 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≥ 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≥ 0 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.
ER  -