Improper colourings inspired by Hadwiger's conjecture

DOI10.1112/JLMS.12127MaRDI QIDQ4584332zbMATH OpenOpenAlexWikidataFDO

Authors Jan van den Heuvel, David R. Wood

Publication date 30 August 2018

Published in Journal of the London Mathematical Society (Search for Journal in Brave)

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

Mathematics Subject Classification ID

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

Abstract: Hadwiger's Conjecture asserts that every $K_t$-minor-free graph has a proper $(t-1)$-colouring. We relax the conclusion in Hadwiger's Conjecture via improper colourings. We prove that every $K_t$-minor-free graph is $(2t-2)$-colourable with monochromatic components of order at most $lceilfrac12(t-2)ceil$. This result has no more colours and much smaller monochromatic components than all previous results in this direction. We then prove that every $K_t$-minor-free graph is $(t-1)$-colourable with monochromatic degree at most $t-2$. This is the best known degree bound for such a result. Both these theorems are based on a decomposition method of independent interest. We give analogous results for $K_{s,t}$-minor-free graphs, which lead to improved bounds on generalised colouring numbers for these classes. Finally, we prove that graphs containing no $K_t$-immersion are $2$-colourable with bounded monochromatic degree.

Recommendations

• Towards a version of Ohba's conjecture for improper colorings
• About a Brooks-type theorem for improper colouring
• Improper C-colorings of graphs
• scientific article; zbMATH DE number 1146231
• The complexity of some acyclic improper colourings
• Fractional coloring and the odd Hadwiger's conjecture
• On a coloring conjecture of Hajós
• Fractional colouring and Hadwiger's conjecture
• Acrylic improper colorings of graphs
• Improper colouring of (random) unit disk graphs

Cited in

(36)

• On monochromatic component size for improper colourings
• Towards a version of Ohba's conjecture for improper colorings
• Immersion and clustered coloring
• Improved bounds for weak coloring numbers
• On coloring numbers of graph powers
• On 2-defective DP-colorings of sparse graphs
• Defective DP-colorings of sparse multigraphs
• Defective DP-colorings of sparse simple graphs
• Clustered variants of Hajós' conjecture
• Coloring immersion-free graphs
• scientific article; zbMATH DE number 1146231 (Why is no real title available?)
• Improper colouring of graphs with no odd clique minor
• Defective and clustered choosability of sparse graphs
• Clustered colouring of graph classes with bounded treedepth or pathwidth
• Improved bound for improper colourings of graphs with no odd clique minor
• Clustered 3-colouring graphs of bounded degree
• Separating layered treewidth and row treewidth
• Odd colourings, conflict-free colourings and strong colouring numbers
• Shallow Minors, Graph Products, and Beyond-Planar Graphs
• On a recolouring version of Hadwiger's conjecture
• Graph product structure for non-minor-closed classes
• Defective coloring of hypergraphs
• Sparse critical graphs for defective DP-colorings
• Coloring hypergraphs with excluded minors
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Colouring strong products
• Product structure of graph classes with bounded treewidth
• Boxicity, poset dimension, and excluded minors
• Reduced bandwidth: a qualitative strengthening of twin-width in minor-closed classes (and beyond)
• Cop-width, flip-width and strong colouring numbers
• The r-dynamic chromatic number is bounded in the strong 2-coloring number
• Sparse critical graphs for defective (1, 3)-coloring
• Clustered colouring of graph products
• Clustered coloring of (path + 2K₁)-free graphs on surfaces
• Subchromatic numbers of powers of graphs with excluded minors
• Hadwiger numbers and over-dominating colourings

This page was built for publication: Improper colourings inspired by Hadwiger's conjecture

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