Improper colouring of graphs with no odd clique minor

DOI10.1017/S0963548318000548zbMath1436.05039arXiv1612.05372OpenAlexW3098333129WikidataQ128451417 ScholiaQ128451417MaRDI QIDQ5222552

Dong Yeap Kang, Sang-il Oum

Publication date: 6 April 2020

Published in: Combinatorics, Probability and Computing (Search for Journal in Brave)

Abstract: As a strengthening of Hadwiger's conjecture, Gerards and Seymour conjectured that every graph with no odd $K_t$ minor is $(t-1)$-colorable. We prove two weaker variants of this conjecture. Firstly, we show that for each $tgeq2$, every graph with no odd $K_t$ minor has a partition of its vertex set into $6t-9$ sets $V_1,dots,V_{6t-9}$ such that each $V_i$ induces a subgraph of bounded maximum degree. Secondly, we prove that for each $tgeq2$, every graph with no odd $K_t$ minor has a partition of its vertex set into $10t-13$ sets $V_1,dots,V_{10t-13}$ such that each $V_i$ induces a subgraph with components of bounded size. The second theorem improves a result of Kawarabayashi (2008), which states that the vertex set can be partitioned into $496t$ such sets.

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

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83) Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69)

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Contractibility and the Hadwiger conjecture
• Lower bound of the Hadwiger number of graphs by their average degree
• A relaxed Hadwiger's conjecture for list colorings
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Defective and clustered graph colouring
• The extremal function for complete minors
• Clustered colouring in minor-closed classes
• Defective colouring of graphs excluding a subgraph or minor
• Even-cycle decompositions of graphs with no odd-\(K_4\)-minor
• On the odd-minor variant of Hadwiger's conjecture
• On the notion of balance of a signed graph
• Hadwiger’s Conjecture
• Defective coloring revisited
• An extremal function for contractions of graphs
• A Relative of Hadwiger's Conjecture
• 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 Choosability and Property B
• Colouring Planar Graphs With Three Colours and No Large Monochromatic Components
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components

Related Items (8)

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 ⋮ Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant ⋮ Clustered variants of Hajós' conjecture ⋮ Fractional coloring and the odd Hadwiger's conjecture ⋮ Clustered coloring of graphs with bounded layered treewidth and bounded degree ⋮ Colouring strong products

This page was built for publication: Improper colouring of graphs with no odd clique minor