Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs
Fuente:
arXiv
Gespeichert in:
| Hauptverfasser: | , |
|---|---|
| Format: | Preprint |
| Veröffentlicht: |
2025
|
| Schlagworte: | |
| Online-Zugang: | |
| Tags: |
Tag hinzufügen
Keine Tags, Fügen Sie den ersten Tag hinzu!
|
| _version_ | 1866912853741535232 |
|---|---|
| author | Bencs, Ferenc Regts, Guus |
| author_facet | Bencs, Ferenc Regts, Guus |
| contents | We prove that for any graph $G$ the (complex) zeros of its chromatic polynomial, $χ_G(x)$, lie inside the disk centered at $0$ of radius $4.25 Δ(G)$, where $Δ(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Δ(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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2505_04366 |
| institution | arXiv |
| publishDate | 2025 |
| record_format | arxiv |
| spellingShingle | Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs Bencs, Ferenc Regts, Guus Combinatorics Discrete Mathematics Data Structures and Algorithms We prove that for any graph $G$ the (complex) zeros of its chromatic polynomial, $χ_G(x)$, lie inside the disk centered at $0$ of radius $4.25 Δ(G)$, where $Δ(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Δ(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. |
| title | Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs |
| topic | Combinatorics Discrete Mathematics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2505.04366 |