Clustered Variants of Hajós' Conjecture

Chun-Hung Liu, David R. Wood

Published 2019-08-14Version 1

Haj\'os conjectured that every graph containing no subdivision of the complete graph $K_{s+1}$ is properly $s$-colorable. This result was disproved by Catlin. Indeed, the maximum chromatic number of such graphs is $\Omega(s^2/\log s)$. In this paper we prove that $O(s)$ colors are enough for a weakening of this conjecture that only requires every monochromatic component to have bounded size (so-called \emph{clustered} coloring). Our approach in this paper leads to more results. Say that a graph is an {\it almost $(\leq 1)$-subdivision} of a graph $H$ if it can be obtained from $H$ by subdividing edges, where at most one edge is subdivided more than once. We prove the following (where $s \geq 2$): \begin{enumerate} \item Graphs of bounded treewidth and with no almost $(\leq 1)$-subdivision of $K_{s+1}$ are $s$-choosable with bounded clustering. \item For every graph $H$, graphs with no $H$-minor and no almost $(\leq 1)$-subdivision of $K_{s+1}$ are $(s+1)$-colorable with bounded clustering. \item For every graph $H$ of maximum degree at most $d$, graphs with no $H$-subdivision and no almost $(\leq 1)$-subdivision of $K_{s+1}$ are $\max\{s+3d-5,2\}$-colorable with bounded clustering. \item For every graph $H$ of maximum degree $d$, graphs with no $K_{s,t}$ subgraph and no $H$-subdivision are $\max\{s+3d-4,2\}$-colorable with bounded clustering. \item Graphs with no $K_{s+1}$-subdivision are $\max\{4s-5,1\}$-colorable with bounded clustering. \end{enumerate} The first result shows that the weakening of Haj\'{o}s' conjecture is true for graphs of bounded treewidth in a stronger sense; the final result is the first $O(s)$ bound on the clustered chromatic number of graphs with no $K_{s+1}$-subdivision.