Hostname: page-component-7b7567c8c-2n9c9 Total loading time: 0 Render date: 2026-11-15T22:05:54.319Z Has data issue: false hasContentIssue false

Squared Chromatic Number Without Claws or Large Cliques

Part of:Graph theory

Published online by Cambridge University Press:  09 January 2019

Wouter Cames van Batenburg
Affiliation:
Computer Science Department, Faculté des Sciences, Université Libre de Bruxelles, Campus de la Plaine, CP212, B-1050 Brussels, Belgium Email: wcamesva@ulb.ac.be
Ross J. Kang
Affiliation:
Department of Mathematics, Radboud University Nijmegen, Postbus 9010, 6500 GL Nijmegen, The Netherlands Email: ross.kang@gmail.com
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Article
Copyright
© Canadian Mathematical Society 2018