Clustered Variants of Hajós' Conjecture
share
Hajós 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 Ω(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 clustered coloring). Our approach in this paper leads to more results. Say that a graph is an almost (≤ 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 ≥ 2): * Graphs of bounded treewidth and with no almost (≤ 1)-subdivision of K_s+1 are s-choosable with bounded clustering. * For every graph H, graphs with no H-minor and no almost (≤ 1)-subdivision of K_s+1 are (s+1)-colorable with bounded clustering. * For every graph H of maximum degree at most d, graphs with no H-subdivision and no almost (≤ 1)-subdivision of K_s+1 are max{s+3d-5,2}-colorable with bounded clustering. * 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. * Graphs with no K_s+1-subdivision are max{4s-5,1}-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.
READ FULL TEXT