Clustered Variants of Hajós' Conjecture

Abstract

Hajós conjectured that every graph containing no subdivision of the complete graph $K_{s+1}$ is properly $s$-colorable. This conjecture was disproved by Catlin. Indeed, the maximum chromatic number of such graphs is $\Omega (s^2/\log s)$. 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 clustered coloring). Our approach leads to more results. Say that a graph is an almost $(\le 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. Note that every graph with no $H$-subdivision does not contain an almost $(\le 1)$-subdivision of $H$. We prove the following (where $s\ge 2$): (1) Graphs of bounded treewidth and with no almost $(\le 1)$-subdivision of $K_{s+1}$ are $s$-choosable with bounded clustering. (2) For every graph $H$, graphs with no $H$-minor and no almost $(\le 1)$-subdivision of $K_{s+1}$ are $(s+1)$-colorable with bounded clustering. (3) For every graph $H$ of maximum degree at most $d$, graphs with no $H$-subdivision and no almost $(\le 1)$-subdivision of $K_{s+1}$ are $\max \{s+3d-5,2\}$-colorable with bounded clustering. (4) 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. (5) Graphs with no $K_{s+1}$-subdivision are $(4s-5)$-colorable with bounded clustering. The first result shows that the weakening of Hajó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.

arXiv admin note: text overlap with arXiv:1905.09495

References in corpus (1)

• Islands in minor-closed classes. I. Bounded treewidth and separators

Cited by in corpus (7)

• Clustered 3-Colouring Graphs of Bounded Degree
• Immersion and clustered coloring
• Colouring Strong Products
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• Defective coloring is perfect for minors
• Weak diameter choosability of graphs with an excluded minor
• The grid-minor theorem revisited