Improper colourings inspired by Hadwiger's conjecture

DOI10.1112/JLMS.12127zbMATH Open1402.05085arXiv1704.06536OpenAlexW3125642972WikidataQ123018537 ScholiaQ123018537MaRDI QIDQ4584332FDOQ4584332

David R. Wood, Jan van den Heuvel

Publication date: 30 August 2018

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

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.

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

Mathematics Subject Classification ID

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

Cited In (24)

• Improved bound for improper colourings of graphs with no odd clique minor
• Separating layered treewidth and row treewidth
• Immersion and clustered coloring
• Clustered colouring of graph classes with bounded treedepth or pathwidth
• Improved bounds for weak coloring numbers
• Product structure of graph classes with bounded treewidth
• Clustered 3-colouring graphs of bounded degree
• Towards a version of Ohba's conjecture for improper colorings
• Graph product structure for non-minor-closed classes
• On coloring numbers of graph powers
• Title not available (Why is that?)
• On 2-defective DP-colorings of sparse graphs
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Colouring strong products
• Title not available (Why is that?)
• Defective coloring of hypergraphs
• Sparse critical graphs for defective DP-colorings
• Improper colouring of graphs with no odd clique minor
• Defective and clustered choosability of sparse graphs
• Clustered variants of Hajós' conjecture
• Defective DP-colorings of sparse multigraphs
• Defective DP-colorings of sparse simple graphs
• Boxicity, poset dimension, and excluded minors
• Shallow Minors, Graph Products, and Beyond-Planar Graphs

Recommendations

• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Title not available (Why is that?) 👍 👎
• Acrylic improper colorings of graphs 👍 👎
• The complexity of some acyclic improper colourings 👍 👎
• Improper C-colorings of graphs 👍 👎
• Towards a version of Ohba's conjecture for improper colorings 👍 👎
• Fractional colouring and Hadwiger's conjecture 👍 👎
• Fractional coloring and the odd Hadwiger's conjecture 👍 👎
• On a coloring conjecture of Hajós 👍 👎

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)