EUVIMEDEUVIMED entdecken
Open Access · CC BY 4.0

Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs

Ferenc Bencs, Guus Regts

Combinatorial Theory · 2026

DOI: 10.5070/c6.69940 ↗

Kurz gefasst

Fachartikel in der Zeitschrift Combinatorial Theory, 2026. Verfasst von Ferenc Bencs und 1 weiteren Autor:innen. Der Volltext ist frei zugänglich (Open Access, CC BY 4.0).

AbstractBibliografische AngabenZitierenVerwandte Studien

Abstract (Originalsprache)

We prove that for any graph \(G\) the (complex) zeros of its chromatic polynomial, \(\chi_G(x)\), lie inside the disk centered at \(0\) of radius \(4.25 \Delta(G)\), where \(\Delta(G)\) denotes the maximum degree of \(G\). This improves on a recent result of Jenssen, Patel and Regts, who proved a bound of \(5.94\Delta(G)\). Moreover, we show that for graphs of sufficiently large girth we can replace \(4.25\) by \(3.60\) and for claw-free graphs we can replace \(4.25\) by \(3.81\). Our proofs add some substantially novel ideas to those developed by Jenssen, Patel, and Regts, while building on them. A key novel ingredient for claw-free graphs is to use a representation of the coefficients of the chromatic polynomial in terms of the number of certain partial acyclic orientations. Mathematics Subject Classifications: 05C31, 68W25 Keywords: Chromatic polynomial, acyclic orientation, complex zeros, broken circuit, maximum degree, claw-free graphs

Zitieren

APA

Bencs, F., & Regts, G. (2026). Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs. Combinatorial Theory. https://doi.org/10.5070/c6.69940

Vancouver

Bencs F, Regts G. Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs. Combinatorial Theory. 2026. doi:10.5070/c6.69940

BibTeX
@article{Bencs2026,
  author = {Bencs, Ferenc and Regts, Guus},
  title = {Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs},
  journal = {Combinatorial Theory},
  year = {2026},
  doi = {10.5070/c6.69940}
}
Kostenlos starten →