Hajos conjectured that every graph containing no subdivision of the complete graph Ks+1 is properly s-colorable. This conjecture was disproved by Catlin. Indeed, the maximum chromatic number of such graphs is Omega(s(2)/logs). 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, many of which only require a much weaker assumption that forbids an 'almost (<= 1)-subdivision' (where at most one edge is subdivided more than once). This assumption is best possible, since no bound on the number of colors exists unless we allow at least one edge to be subdivided arbitrarily many times. We prove the following (where s >= 2): 1. Graphs of bounded treewidth and with no almost (<= 1)-subdivision of Ks+1 are s-choosable with bounded clustering. 2. For every graph H, graphs with no H -minor and no almost (<= 1)-subdivision of Ks+1 are (s + 1)-colorable with bounded clustering. 3. For every graph H of maximum degree at most d, graphs with no H -sub division and no almost (<= 1)-subdivision of Ks+1 are max{s + 3d - 5, 2}-colorable with bounded clustering. 4. For every graph H of maximum degree d, graphs with no Ks,t subgraph and no H -sub division are max{s + 3d - 4, 2}-colorable with bounded clustering. 5. Graphs with no Ks+1-subdivision are (4s - 5)-colorable with bounded clustering. The first result is tight and shows that the clustered analogue of Hajos' conjecture is true for graphs of bounded treewidth. The second result implies an upper bound for the clustered version of Hadwiger's conjecture that is only one color away from the known lower bound, and shows that the number of colors is independent of the forbidden minor. The final result is the first O(s) bound on the clustered chromatic number of graphs with no Ks+1-sub division. (C) 2021 Elsevier Inc. All rights reserved.
NSTL
Elsevier
