Squared Chromatic Number Without Claws or Large Cliques

• Published in: Canadian mathematical bulletin 2019-03, Vol.62 (1), p.23-35
• Main Authors: Cames van Batenburg, Wouter, Kang, Ross J.
• Format: Article
• Language: English
• Subjects: Apexes; Graph theory; Graphs
• ISSN: 0008-4395; 1496-4287
• DOI: 10.4153/CMB-2018-024-5

Let $G$ be a claw-free graph on $n$ vertices with clique number $\unicode[STIX]{x1D714}$ , and consider the chromatic number $\unicode[STIX]{x1D712}(G^{2})$ of the square $G^{2}$ of $G$ . Writing $\unicode[STIX]{x1D712}_{s}^{\prime }(d)$ for the supremum of $\unicode[STIX]{x1D712}(L^{2})$ over the line graphs $L$ of simple graphs of maximum degree at most $d$ , we prove that $\unicode[STIX]{x1D712}(G^{2})\leqslant \unicode[STIX]{x1D712}_{s}^{\prime }(\unicode[STIX]{x1D714})$ for $\unicode[STIX]{x1D714}\in \{3,4\}$ . For $\unicode[STIX]{x1D714}=3$ , this implies the sharp bound $\unicode[STIX]{x1D712}(G^{2})\leqslant 10$ . For $\unicode[STIX]{x1D714}=4$ , this implies $\unicode[STIX]{x1D712}(G^{2})\leqslant 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.