Paperlane

no. 12 · Tuesday 10 November 2026

Vu's conjecture holds for claw-free graphs

Linda Cook, Ross J. Kang, Eileen Robinson and Gabriëlle Zwaneveld

math.CO · v3 · 34 pp

Abstract

Given a graph $G$, let $Δ_2(G)$ denote the maximum number of neighbors any two distinct vertices of $G$ have in common. Vu (2002) proposed that, provided $Δ_2(G)$ is not too small as a proportion of the maximum degree $Δ(G)$ of $G$, the chromatic number of $G$ should never be too much larger than $Δ_2(G)$. We make a first approach towards Vu's conjecture from a structural graph theoretic point of view. We prove that, in the case where $G$ is claw-free, indeed the chromatic number of $G$ is at most $Δ_2(G)+3$. This is tight, as our bound is met with equality for the line graph of the Petersen graph. Moreover, we can prove this in terms of the more specific parameter that bounds the maximum number of neighbors any two endpoints of some edge of $G$ have in common. Our result may be viewed as a generalization of the classic bound of Vizing (1964) for edge-coloring.

comments
34 pages, 7 figures; v3 is AAM to appear in Canadian Journal of Mathematics
fields
Combinatorics
pdf ↗ page arXiv:2510.15553 ↗