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

(29)

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

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)