A relative of Hadwiger's conjecture

DOI10.1137/141002177MaRDI QIDQ3461983zbMATH OpenOpenAlexWikidataFDO

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)

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

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)

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.

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

Cites work

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

Cited in

(27)

• Immersion and clustered coloring
• Improved bound for improper colourings of graphs with no odd clique minor
• scientific article; zbMATH DE number 54802 (Why is no real title available?)
• 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
• On 2-defective DP-colorings of sparse graphs
• Fractional colouring and Hadwiger's conjecture
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Colouring strong products
• Packing seagulls
• On a new reformulation of Hadwiger's conjecture
• Hadwiger's conjecture
• Defective coloring of hypergraphs
• Sparse critical graphs for defective DP-colorings
• A relaxation of the Bordeaux conjecture
• Improper colouring of graphs with no odd clique minor
• Defective and clustered choosability of sparse graphs
• Partitioning \(H\)-minor free graphs into three subgraphs with no large components
• Clustered variants of Hajós' conjecture
• Defective DP-colorings of sparse multigraphs
• An inequality about pairs of conjugate Hölder numbers
• Defective DP-colorings of sparse simple graphs
• Refined List Version of Hadwiger’s Conjecture

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)