Improper colouring of graphs with no odd clique minor

DOI10.1017/S0963548318000548MaRDI QIDQ5222552zbMATH OpenOpenAlexWikidataFDO

Authors Dong Yeap Kang, Sang-Il Oum

Publication date 6 April 2020

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

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

Mathematics Subject Classification ID

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

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.

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

Cites work

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

Cited in

(15)

• Note on coloring graphs without odd-\(K_k\)-minors
• No odd pairs in minimal imperfect NP\({}_{5}\) graphs.
• Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant
• A new upper bound on the chromatic number of graphs with no odd \(K_t\) minor
• Fractional coloring and the odd Hadwiger's conjecture
• Clustered variants of Hajós' conjecture
• 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
• Clustered coloring of graphs with bounded layered treewidth and bounded degree
• Colouring strong products
• Clustered colouring of odd-H-minor-free graphs
• Defective and clustered colouring of graphs with given girth
• Clustered coloring of graphs excluding a subgraph and a minor
• Some remarks on the odd Hadwiger's conjecture

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)