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

preprint2026arXivOpen access

Abstract

Given a claw-free graph G=(V,E)G=(V,E) with maximum degree ΔΔ, we define the parameter κ∈[0,1]κ\in [0,1] as κ=max⁡v∈V∣Iv∣⌊Δ2/4⌋κ={\max_{v\in V}|I_v|\over \lfloorΔ^2/4\rfloor} where IvI_v is the set of all independent pairs in the neighborhood of vv. We refer to κκ as the pair independence ratio of GG. We prove that for any claw-free graph GG with pair independence ratio at most κκ the zeros of its chromatic polynomial PG(q)P_G(q) lie inside the disk D={q∈C: ∣q∣<Cκ0Δ}D=\{q\in \mathbb{C}:~|q|< C_κ^0Δ\}, where Cκ0C_κ^0 is an increasing function of κ∈[0,1]κ\in [0,1]. If GG is also square-free and diamond free, the function Cκ0C_κ^0 can be replaced by a sharper function Cκ1C_κ^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''.

Explore this paper’s authors, topics and related work.

Building this map preview

BZPEER is loading the nearby papers, people, topics and institutions for this page.

Reviews 0

Write a reviewWrite

No reviews yet.

Discussion 0

Add a commentWrite

No comments yet.