Clustered variants of Hajós' conjecture

DOI10.1016/J.JCTB.2021.09.002MaRDI QIDQ2664549zbMATH OpenOpenAlexFDO

Authors Chun-Hung Liu, David R. Wood

Publication date 17 November 2021

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

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

zbMATH Keywords

clustered coloringgraph coloringtopological minors

Mathematics Subject Classification ID

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

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.

Recommendations

• Clustered families and applications to Lang‐type conjectures
• scientific article; zbMATH DE number 99004
• Towards the Hanani-Tutte theorem for clustered graphs
• Varieties of clusters and Enriques diagrams
• Clusters and various versions of Wiener-type invariants
• A remark on the cluster theorem
• scientific article; zbMATH DE number 1302890
• New families of n-clusters verifying the Erdős-Faber-Lovász conjecture
• Some remarks on Hajós' conjecture
• Cluster expansion and the boxdot conjecture

Cites work

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

Cited in

(15)

• Immersion and clustered coloring
• Clustered colouring in minor-closed classes
• Chromatic number, clique subdivisions, and the conjectures of Hajós and Erdős-Fajtlowicz
• A global decomposition theorem for excluding immersions in graphs with no edge-cut of order three
• List-coloring graphs without subdivisions and without immersions
• On the Clustering Conjecture for Bernoulli Factors of Bernoulli Shifts
• Clustered colouring of graph classes with bounded treedepth or pathwidth
• Clustered 3-colouring graphs of bounded degree
• Separating layered treewidth and row treewidth
• Packing topological minors half‐integrally
• Colouring strong products
• Clustered colouring of odd-H-minor-free graphs
• Weak diameter choosability of graphs with an excluded minor
• Defective and clustered colouring of graphs with given girth
• Clustered coloring of graphs excluding a subgraph and a minor

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

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2664549)