Any 7-chromatic graph has K₇ or K₄,4 as a minor

DOI10.1007/S00493-005-0019-1MaRDI QIDQ2387186zbMATH OpenOpenAlexFDO

Authors Ken-ichi Kawarabayashi, Bjarne Toft

Publication date 26 January 2006

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-005-0019-1

Mathematics Subject Classification ID

Coloring of graphs and hypergraphs (05C15) Graph minors (05C83)

Recommendations

• Hadwiger's conjecture for \(K_ 6\)-free graphs
• Coloring graphs with forbidden minors
• A short proof of a theorem of dirac's about hadwiger's conjecture
• Case 6 of Hadwiger's conjecture. III: The problem of 7-vertices
• Hadwiger's conjecture

Cited in

(26)

• Hadwiger's conjecture for proper circular arc graphs
• Linear connectivity forces large complete bipartite minors
• Note on coloring graphs without odd-\(K_k\)-minors
• List-coloring graphs without \(K_{4,k}\)-minors
• Cliques, minors and apex graphs
• Hadwiger's conjecture for squares of 2-trees
• On the structure of \(k\)-connected graphs without \(K_{k}\)-minor
• Rooted minor problems in highly connected graphs
• On group choosability of graphs. II
• Rooted topological minors on four vertices
• Coloring graphs with forbidden minors
• Sketchy tweets: ten minute conjectures in graph theory
• Fractional coloring and the odd Hadwiger's conjecture
• The extremal function for \(K_{8}^{-}\) minors
• Properties of 8-contraction-critical graphs with no K₇ minor
• Hadwiger's conjecture and squares of chordal graphs
• A Weakening of the Odd Hadwiger's Conjecture
• Hadwiger's conjecture for graphs with forbidden holes
• List-coloring graphs without subdivisions and without immersions
• Graph pattern detection: hardness for all induced patterns and faster noninduced cycles
• Bipartite graphs with no \(K_6\) minor
• Connectivities for k-knitted graphs and for minimal counterexamples to Hadwiger's conjecture
• On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture
• Some recent progress and applications in graph minor theory
• A relaxed Hadwiger's conjecture for list colorings
• Some remarks on the odd Hadwiger's conjecture

This page was built for publication: Any 7-chromatic graph has \(K_7\) or \(K_{4,4}\) as a minor

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