On Tutte's extension of the four-colour problem

DOI10.1016/S0095-8956(81)80013-5zbMath0471.05031MaRDI QIDQ1157338

P. D. Seymour

Publication date: 1981

Published in: Journal of Combinatorial Theory. Series B (Search for Journal in Brave)

zbMATH Keywords

Hadwiger's conjectureachromatechain-groupk-flow

Mathematics Subject Classification ID

Combinatorial aspects of matroids and geometric lattices (05B35) Coloring of graphs and hypergraphs (05C15)

Related Items

Between Proper and Strong Edge-Colorings of Subcubic Graphs ⋮ A sufficient condition for edge 6-colorable planar graphs with maximum degree 6 ⋮ Fractional and integral colourings ⋮ Parsimonious edge coloring ⋮ The max-cut problem on graphs not contractible to \(K_ 5\) ⋮ Homomorphisms and edge-colourings of planar graphs ⋮ On Tutte polynomials of matroids representable over \(GF(q)\) ⋮ Between proper and strong edge‐colorings of subcubic graphs ⋮ Double Vizing fans in critical class two graphs ⋮ Decomposition of regular matroids ⋮ Mapping planar graphs into the Coxeter graph ⋮ Some snarks are worse than others ⋮ Nowhere-zero 3-flows in matroid base graph ⋮ Excluding Minors in Cubic Graphs ⋮ Graph edge coloring: a survey ⋮ Integer 4-flows and cycle covers ⋮ The contributions of W.T. Tutte to matroid theory ⋮ Note on cycle double covers of graphs ⋮ Snarks with given real flow numbers ⋮ Fractional Coloring Methods with Applications to Degenerate Graphs and Graphs on Surfaces ⋮ Flows, flow-pair covers and cycle double covers ⋮ Homomorphisms of triangle-free graphs without a \(K_{5}\)-minor ⋮ Note on integer 4-flows in graphs ⋮ Fulkerson-covers of hypohamiltonian graphs

Cites Work

• Unnamed Item
• Flows and generalized coloring theorems in graphs
• Decomposition of regular matroids
• Nowhere-zero 6-flows
• Hajos' graph-coloring conjecture: Variations and counterexamples
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Colouring problems
• Beweis einer Abschwächung der Hadwiger-Vermutung
• On the algebraic theory of graph colorings
• A Quick Proof of Wagner's Equivalence Theorem
• A Property of 4-Chromatic Graphs and some Remarks on Critical Graphs
• A Contribution to the Theory of Chromatic Polynomials