Hadwiger's conjecture for \(K_ 6\)-free graphs

DOI10.1007/BF01202354zbMath0830.05028OpenAlexW1520619927WikidataQ55881141 ScholiaQ55881141MaRDI QIDQ1311018

Neil Robertson, Robin Thomas, P. D. Seymour

Publication date: 18 January 1996

Published in: Combinatorica (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1007/bf01202354

zbMATH Keywords

chromatic numberplanarHadwiger's conjecturefour-colour theoremcontractiblefour-colour conjecturetheorem of Wagner

Mathematics Subject Classification ID

Structural characterization of families of graphs (05C75) Coloring of graphs and hypergraphs (05C15)

Related Items (only showing first 100 items - show all)

Clique minors in graphs with a forbidden subgraph ⋮ Oriented cobicircular matroids are \textit{GSP} ⋮ Weakening total coloring conjecture and Hadwiger's conjecture on total graphs ⋮ Strengthening Hadwiger's conjecture for 4- and 5-chromatic graphs ⋮ Bipartite graphs with no \(K_6\) minor ⋮ Local Hadwiger's conjecture ⋮ On 2-cycles of graphs ⋮ Refined List Version of Hadwiger’s Conjecture ⋮ Recent progress towards Hadwiger's conjecture ⋮ Coloring hypergraphs with excluded minors ⋮ Biclique immersions in graphs with independence number 2 ⋮ Hadwiger's conjecture and topological bounds ⋮ Some excluded minors for the spindle surface ⋮ The high order spectral extremal results for graphs and their applications ⋮ On the choosability of \(H\)-minor-free graphs ⋮ Bicircular matroids are 3-colorable ⋮ Improved bound for improper colourings of graphs with no odd clique minor ⋮ Strong complete minors in digraphs ⋮ Improved lower bound for the list chromatic number of graphs with no K_t minor ⋮ Dynamic coloring of graphs having no \(K_5\) minor ⋮ Asymptotic equivalence of Hadwiger's conjecture and its odd minor-variant ⋮ Excluded-minor characterization of apex-outerplanar graphs ⋮ Rooted minor problems in highly connected graphs ⋮ Hadwiger's conjecture for squares of 2-trees ⋮ Graph theory -- a survey on the occasion of the Abel Prize for László Lovász ⋮ A note on the Hadwiger number of circular arc graphs ⋮ A special case of Hadwiger's conjecture ⋮ Coloring immersion-free graphs ⋮ A Relative of Hadwiger's Conjecture ⋮ On a new reformulation of Hadwiger's conjecture ⋮ On the connectivity of minimum and minimal counterexamples to Hadwiger's conjecture ⋮ Constructing Graphs with No Immersion of Large Complete Graphs ⋮ Some remarks on even-hole-free graphs ⋮ Hadwiger's conjecture for circular colorings of edge-weighted graphs ⋮ On the Hadwiger's conjecture for graph products ⋮ On the connection between the chromatic number of a graph and the number of cycles covering a vertex or an edge ⋮ Clique immersion in graphs without a fixed bipartite graph ⋮ Coloring graphs with forbidden minors ⋮ Some recent progress and applications in graph minor theory ⋮ Linking four vertices in graphs of large connectivity ⋮ Distance constraints in graph color extensions ⋮ A relaxed Hadwiger's conjecture for list colorings ⋮ Rooted \(K_4\)-minors ⋮ A minimum degree condition forcing complete graph immersion ⋮ Hadwiger's Conjecture for Graphs with Forbidden Holes ⋮ \(K_{6}\) minors in 6-connected graphs of bounded tree-width ⋮ Finite duality for some minor closed classes ⋮ Hadwiger's Conjecture for the Complements of Kneser Graphs ⋮ Linkless and flat embeddings in 3-space ⋮ Phase transition of degeneracy in minor-closed families ⋮ Sketchy tweets: ten minute conjectures in graph theory ⋮ Optimal connectivity for fat-triangle linkages ⋮ Graph theory. Abstracts from the workshop held January 2--8, 2022 ⋮ Some connectivity properties for excluded minors of the graph invariant \(\nu(G)\) ⋮ Large minors in graphs with given independence number ⋮ Breaking the degeneracy barrier for coloring graphs with no \(K_t\) minor ⋮ Properties of 8-contraction-critical graphs with no \(K_7\) minor ⋮ Parameters Tied to Treewidth ⋮ Hadwiger's Conjecture for ℓ‐Link Graphs ⋮ Forcing clique immersions through chromatic number ⋮ All minor-minimal apex obstructions with connectivity two ⋮ In memoriam: Professor Robin Thomas (1962--2020) ⋮ Random Graphs from a Minor-Closed Class ⋮ Hadwiger's conjecture for inflations of 3-chromatic graphs ⋮ Rooted complete minors in line graphs with a Kempe coloring ⋮ Odd complete minors in even embeddings on surfaces ⋮ An introduction to the discharging method via graph coloring ⋮ Complete partitions of graphs ⋮ Some remarks on the odd Hadwiger's conjecture ⋮ Complete graph immersions in dense graphs ⋮ Fractional coloring and the odd Hadwiger's conjecture ⋮ \(K_{6}\) minors in large 6-connected graphs ⋮ A basic elementary extension of the Duchet-Meyniel theorem ⋮ Structure of 4-connected claw-free graphs not containing a subdivision of \(K_{5}\) ⋮ On clique immersions in line graphs ⋮ On the structure of \(k\)-connected graphs without \(K_{k}\)-minor ⋮ The extremal function for \(K_{9}\) minors ⋮ On group choosability of graphs. II ⋮ Contractibility and the Hadwiger conjecture ⋮ On topological relaxations of chromatic conjectures ⋮ Reducing Hajós' 4-coloring conjecture to 4-connected graphs ⋮ A Weakening of the Odd Hadwiger's Conjecture ⋮ Minors in Graphs with High Chromatic Number ⋮ PARTIAL RESULT ON HADWIGER'S CONJECTURE ⋮ Hadwiger's conjecture for 3-arc graphs ⋮ Maximal ambiguously \(k\)-colorable graphs ⋮ Simple graphs of order 12 and minimum degree 6 contain \(K_6\) minors ⋮ On the odd-minor variant of Hadwiger's conjecture ⋮ The edge version of Hadwiger's conjecture ⋮ Connectivities for \(k\)-knitted graphs and for minimal counterexamples to Hadwiger's conjecture ⋮ Hadwiger number and the Cartesian product of graphs ⋮ Hadwiger’s Conjecture and Squares of Chordal Graphs ⋮ THE CLIQUE MINOR OF GRAPHS WITH INDEPENDENCE NUMBER TWO ⋮ Improper colouring of graphs with no odd clique minor ⋮ Notes on tree- and path-chromatic number ⋮ Hadwiger's conjecture for proper circular arc graphs ⋮ Hadwiger’s Conjecture ⋮ Linear connectivity forces large complete bipartite minors ⋮ Note on coloring graphs without odd-\(K_k\)-minors ⋮ List-coloring graphs without \(K_{4,k}\)-minors

Cites Work

• Unnamed Item
• Hadwiger's conjecture (ḵ\(=6):\) Neighbour configurations of 6-vertices in contraction-critical graphs
• Disjoint paths in graphs
• 2-linked graphs
• Conjecture de Hadwiger: \(k=6\). II: Réductions de sommets de degré 6 dans les graphes 6-chromatiques contraction-critiques. (Hardwiger's conjecture: \(k=6\). II: Reductions of 6-vertices in 6-chromatic contraction-critical graphs)
• Über die Maximalzahl kreuzungsfreier H-Wege
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Graph minors. IX: Disjoint crossed paths
• Homomorphiesätze für Graphen
• Über trennende Eckenmengen in homomorphiekritischen Graphen
• A Polynomial Solution to the Undirected Two Paths Problem
• The Factorization of Linear Graphs
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs

This page was built for publication: Hadwiger's conjecture for \(K_ 6\)-free graphs