Clustered Coloring of Graphs Excluding a Subgraph and a Minor

Abstract

A graph coloring has bounded clustering if each monochromatic component has bounded size. Equivalently, it is a partition of the vertices into induced subgraphs with bounded size components. This paper studies clustered colorings of graphs, where the number of colors depends on an excluded minor and/or an excluded subgraph. We prove the following results (for fixed integers $s,t$ and a fixed graph $H$). First we show that graphs with no $K_{s,t}$ subgraph and with no $H$-minor are $(s+2)$-colorable with bounded clustering. The number of colors here is best possible. This result implies that graphs with no $K_{s+1}$-minor are $(s+2)$-colorable with bounded clustering, which is within two colors of the clustered coloring version of Hadwiger's conjecture. For graphs of bounded treewidth (or equivalently, excluding a planar minor) and with no $K_{s,t}$ subgraph, we prove $(s+1)$-choosability with bounded clustering, which is best possible. We then consider excluding an odd minor. We prove that graphs with no $K_{s,t}$ subgraph and with no odd $H$-minor are $(2s+1)$-colorable with bounded clustering, generalizing a result of the first author and Oum who proved the case $s=1$. Moreover, at least $s-1$ color classes are stable sets. Finally, we consider the clustered coloring version of a conjecture of Gerards and Seymour and prove that graphs with no odd $K_{s+1}$-minor are $(8s-4)$-colorable with bounded clustering, which improves on previous such bounds.

References in corpus (5)

• Breaking the degeneracy barrier for coloring graphs with no $K_t$ minor
• Islands in minor-closed classes. I. Bounded treewidth and separators
• Clustered Graph Coloring and Layered Treewidth
• Clustered Variants of Hajós' Conjecture
• Further Progress towards the List and Odd Versions of Hadwiger's Conjecture

Cited by in corpus (7)

• Clustered 3-Colouring Graphs of Bounded Degree
• Clustered Graph Coloring and Layered Treewidth
• Clustered Variants of Hajós' Conjecture
• Separating layered treewidth and row treewidth
• Immersion and clustered coloring
• Colouring Strong Products
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three