Squared chromatic number without claws or large cliques

Abstract

Let $G$ be a claw-free graph on $n$ vertices with clique number $\omega$, and consider the chromatic number $\chi (G^2)$ of the square $G^2$ of $G$. Writing ${\chi }_s^{\prime }(d)$ for the supremum of $\chi (L^2)$ over the line graphs $L$ of simple graphs of maximum degree at most $d$, we prove that $\chi (G^2)\le {\chi }_s^{\prime }(\omega )$ for $\omega \in \{3,4\}$. For $\omega =3$, this implies the sharp bound $\chi (G^2)\le 10$. For $\omega =4$, this implies $\chi (G^2)\le 22$, which is within $2$ of the conjectured best bound. This work is motivated by a strengthened form of a conjecture of Erdős and Nešetřil.

13 pages; v2 corrects for a subtlety in the original derivation of Thm 1.2; v3 accepted to Canadian Mathematical Bulletin

Cited by in corpus (1)

• An improved procedure for colouring graphs of bounded local density