2019/05/23 by Chun‐Hung Liu, David R. Wood, Liu, Chun-Hung +1
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1905.09495
openalex publication_date 2019/05/23 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 Ks,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 Ks+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 Ks,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 Ks,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 Ks+1-minor are (8s-4)-colorable with bounded clustering, which improves on previous such bounds.