Improper colouring of graphs with no odd clique minor

DOI10.1017/S0963548318000548zbMATH Open1436.05039arXiv1612.05372OpenAlexW3098333129WikidataQ128451417 ScholiaQ128451417MaRDI QIDQ5222552FDOQ5222552

Authors: 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

Recommendations

• Improved bound for improper colourings of graphs with no odd clique minor
• A Weakening of the Odd Hadwiger's Conjecture
• Some remarks on the odd Hadwiger's conjecture
• A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor
• Improper colourings inspired by Hadwiger's conjecture

Mathematics Subject Classification ID

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

Cites Work

• Graph theory
• On the notion of balance of a signed graph
• The extremal function for complete minors
• Hadwiger's conjecture
• Title not available (Why is that?)
• An extremal function for contractions of graphs
• Title not available (Why is that?)
• Lower bound of the Hadwiger number of graphs by their average degree
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• On the odd-minor variant of Hadwiger's conjecture
• Title not available (Why is that?)
• Proof of a conjecture of Mader, Erdős and Hajnal on topological complete subgraphs
• Topological cliques in graphs II
• Defective coloring revisited
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Improper choosability and property B
• Colouring planar graphs with three colours and no large monochromatic components
• A Weakening of the Odd Hadwiger's Conjecture
• Improper colourings inspired by Hadwiger's conjecture
• Contractibility and the Hadwiger conjecture
• A relaxed Hadwiger's conjecture for list colorings
• Defective and clustered graph colouring
• Even-cycle decompositions of graphs with no odd-\(K_4\)-minor
• A relative of Hadwiger's conjecture
• Clustered colouring in minor-closed classes
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Defective colouring of graphs excluding a subgraph or minor
• Colourings with Bounded Monochromatic Components in Graphs of Given Circumference

Cited In (12)

• Improved bound for improper colourings of graphs with no odd clique minor
• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
• A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor
• Clustered colouring of graph classes with bounded treedepth or pathwidth
• Clustered 3-colouring graphs of bounded degree
• Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant
• Some remarks on the odd Hadwiger's conjecture
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Colouring strong products
• Fractional coloring and the odd Hadwiger's conjecture
• Clustered variants of Hajós' conjecture
• Note on coloring graphs without odd-\(K_k\)-minors

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

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