Clustered variants of Hajós' conjecture

DOI10.1016/J.JCTB.2021.09.002zbMath1479.05113arXiv1908.05597OpenAlexW2969015717MaRDI QIDQ2664549

David R. Wood, Chun-Hung Liu

Publication date: 17 November 2021

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

Abstract: Haj'os 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/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. Say that a graph is an almost $(leq1)$-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 $(leq1)$-subdivision of $H$. We prove the following (where $sgeq2$): (1) Graphs of bounded treewidth and with no almost $(leq1)$-subdivision of $K_{s+1}$ are $s$-choosable with bounded clustering. (2) For every graph $H$, graphs with no $H$-minor and no almost $(leq1)$-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 $(leq1)$-subdivision of $K_{s+1}$ are $maxs+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 $maxs+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'{o}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.

Full work available at URL: https://arxiv.org/abs/1908.05597

zbMATH Keywords

graph coloringtopological minorsclustered coloring

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Cites Work

• Some remarks on Hajós' conjecture
• Contractibility and the Hadwiger conjecture
• A relaxed Hadwiger's conjecture for list colorings
• Graph minors. V. Excluding a planar graph
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Bounded size components -- partitions and transversals.
• Partitioning into graphs with only small components
• Excluding subdivisions of bounded degree graphs
• Defective and clustered graph colouring
• On the conjecture of Hajos
• Clustered colouring in minor-closed classes
• Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
• Hadwiger’s Conjecture
• Graph Theory and Probability
• A Relative of Hadwiger's Conjecture
• Graph coloring with no large monochromatic components
• A Weakening of the Odd Hadwiger's Conjecture
• Improper colourings inspired by Hadwiger's conjecture
• Colourings with Bounded Monochromatic Components in Graphs of Given Circumference
• Topological cliques in graphs II
• Improper colouring of graphs with no odd clique minor
• Defective and clustered choosability of sparse graphs
• Improper coloring of graphs on surfaces
• Colouring Planar Graphs With Three Colours and No Large Monochromatic Components
• Islands in Graphs on Surfaces
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Triangulations and the Hajós conjecture

Related Items (8)

Clustered colouring of graph classes with bounded treedepth or pathwidth ⋮ Clustered 3-colouring graphs of bounded degree ⋮ A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three ⋮ Separating layered treewidth and row treewidth ⋮ Packing topological minors half‐integrally ⋮ Colouring strong products ⋮ On the Clustering Conjecture for Bernoulli Factors of Bernoulli Shifts ⋮ Immersion and clustered coloring

This page was built for publication: Clustered variants of Hajós' conjecture