On the zero-free region for the chromatic polynomial of claw-free graphs with and without induced square and induced diamond

Read full text
Authors: Paula M. S. Fialho, Aldo Procacci
Cited by: 0

Abstract

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''.

Fields of Study & Subjects

Advanced Graph Theory Research Graph theory and applications Limits and Structures in Graph Theory

Publication details

Journal / source
arXiv (Cornell University)
Publication date
11 January 2026
Document type
Preprint