A relative of Hadwiger's conjecture

DOI10.1137/141002177zbMATH Open1328.05063arXiv1407.5236OpenAlexW2109001973WikidataQ122950786 ScholiaQ122950786MaRDI QIDQ3461983FDOQ3461983

Authors: Katherine Edwards, Dong Yeap Kang, Sang-Il Oum, Jaehoon Kim, Paul Seymour 

Publication date: 4 January 2016

Published in: SIAM Journal on Discrete Mathematics (Search for Journal in Brave)

Abstract: Hadwiger's conjecture asserts that if a simple graph $G$ has no $K_{t+1}$ minor, then its vertex set $V(G)$ can be partitioned into $t$ stable sets. This is still open, but we prove under the same hypotheses that $V(G)$ can be partitioned into $t$ sets $X_1,ldots,X_t$, such that for $1leilet$, the subgraph induced on $X_i$ has maximum degree at most a function of $t$. This is sharp, in that the conclusion becomes false if we ask for a partition into $t-1$ sets with the same property.

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

Recommendations

• A special case of Hadwiger's conjecture
• A relaxed Hadwiger's conjecture for list colorings
• scientific article; zbMATH DE number 54802
• Matchings and Hadwiger's conjecture
• Hadwiger's conjecture

zbMATH Keywords

Hadwiger's conjectureminorimproper coloring

Mathematics Subject Classification ID

Vertex degrees (05C07) Coloring of graphs and hypergraphs (05C15) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Graph minors (05C83)

Cites Work

• The extremal function for complete minors
• Title not available (Why is that?)
• An extremal function for contractions of graphs
• Lower bound of the Hadwiger number of graphs by their average degree
• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Title not available (Why is that?)
• Defective coloring revisited
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Partitioning into graphs with only small components
• Contractibility and the Hadwiger conjecture
• A relaxed Hadwiger's conjecture for list colorings

Cited In (27)

• Improved bound for improper colourings of graphs with no odd clique minor
• Immersion and clustered coloring
• Title not available (Why is that?)
• Clustered colouring of graph classes with bounded treedepth or pathwidth
• Clustered 3-colouring graphs of bounded degree
• A special case of Hadwiger's conjecture
• Contractibility and the Hadwiger conjecture
• A relaxed Hadwiger's conjecture for list colorings
• Inclusion relations between some congruences related to the dot-depth hierarchy
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• On 2-defective DP-colorings of sparse graphs
• Fractional colouring and Hadwiger's conjecture
• Colouring strong products
• Packing seagulls
• Defective coloring of hypergraphs
• Sparse critical graphs for defective DP-colorings
• Hadwiger's conjecture
• On a new reformulation of Hadwiger's conjecture
• Improper colouring of graphs with no odd clique minor
• Defective and clustered choosability of sparse graphs
• A relaxation of the Bordeaux conjecture
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Clustered variants of Hajós' conjecture
• Refined List Version of Hadwiger’s Conjecture
• An inequality about pairs of conjugate Hölder numbers
• Defective DP-colorings of sparse multigraphs
• Defective DP-colorings of sparse simple graphs

This page was built for publication: A relative of Hadwiger's conjecture

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