On the zero-free region for the chromatic polynomial of claw-free graphs with and without induced square and induced diamond
Fuente:
arXiv
Saved in:
| Main Authors: | , |
|---|---|
| Format: | Preprint |
| Published: |
2026
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866909987423387648 |
|---|---|
| author | Fialho, Paula M. S. Procacci, Aldo |
| author_facet | Fialho, Paula M. S. Procacci, Aldo |
| contents | Given a claw-free graph $G=(V,E)$ with maximum degree $Δ$,
we define the parameter $κ\in [0,1]$ as $κ={\max_{v\in V}|I_v|\over \lfloorΔ^2/4\rfloor}$ where $I_v$ is the set of all independent pairs in the neighborhood of $v$. We refer to $κ$ as the pair independence ratio of $G$.
We prove that for any claw-free graph $G$ with pair independence ratio at most $κ$ the zeros of its chromatic polynomial $P_G(q)$ lie inside the disk $D=\{q\in \mathbb{C}:~|q|< C_κ^0Δ\}$, where $C_κ^0$ is an increasing function of $κ\in [0,1]$. If $G$ is also square-free and diamond free, the function $C_κ^0$ can be replaced by a sharper function $C_κ^1$. These bounds constitute an improvement upon results
recently given by Bencs and Regts in ''Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs''. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2601_06918 |
| institution | arXiv |
| publishDate | 2026 |
| record_format | arxiv |
| spellingShingle | On the zero-free region for the chromatic polynomial of claw-free graphs with and without induced square and induced diamond Fialho, Paula M. S. Procacci, Aldo Combinatorics 05C31 Given a claw-free graph $G=(V,E)$ with maximum degree $Δ$, we define the parameter $κ\in [0,1]$ as $κ={\max_{v\in V}|I_v|\over \lfloorΔ^2/4\rfloor}$ where $I_v$ is the set of all independent pairs in the neighborhood of $v$. We refer to $κ$ as the pair independence ratio of $G$. We prove that for any claw-free graph $G$ with pair independence ratio at most $κ$ the zeros of its chromatic polynomial $P_G(q)$ lie inside the disk $D=\{q\in \mathbb{C}:~|q|< C_κ^0Δ\}$, where $C_κ^0$ is an increasing function of $κ\in [0,1]$. If $G$ is also square-free and diamond free, the function $C_κ^0$ can be replaced by a sharper function $C_κ^1$. These bounds constitute an improvement upon results recently given by Bencs and Regts in ''Improved bounds on the zeros of the chromatic polynomial of graphs and claw-free graphs''. |
| title | On the zero-free region for the chromatic polynomial of claw-free graphs with and without induced square and induced diamond |
| topic | Combinatorics 05C31 |
| url | https://arxiv.org/abs/2601.06918 |