Edge-colouring eight-regular planar graphs

DOI10.1016/J.JCTB.2015.05.002MaRDI QIDQ491001zbMATH OpenOpenAlexFDO

Authors Maria Chudnovsky, Katherine Edwards, Paul Seymour

Publication date 21 August 2015

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

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

zbMATH Keywords

planar graphedge colouringfour-colour theoremdischargingreducible configuration

Mathematics Subject Classification ID

Planar graphs; geometric and topological aspects of graph theory (05C10) Coloring of graphs and hypergraphs (05C15)

Abstract: It was conjectured by the third author in about 1973 that every $d$-regular planar graph (possibly with parallel edges) can be $d$-edge-coloured, provided that for every odd set $X$ of vertices, there are at least $d$ edges between $X$ and its complement. For $d=3$ this is the four-colour theorem, and the conjecture has been proved for all $dle7$, by various authors. Here we prove it for $d=8$.

Recommendations

• Edge-colouring seven-regular planar graphs
• Edge-colouring of regular graphs of large degree
• scientific article; zbMATH DE number 3970775
• Planar graphs with maximum degree D at least 8 are (D+1)-edge-choosable
• Edge coloring regular graphs of high degree

Cites work

• Edge-colouring seven-regular planar graphs
• Every planar map is four colorable. I: Discharging
• Every planar map is four colorable. II: Reducibility
• Packing six \(T\)-joins in plane graphs
• The four-colour theorem

Cited in

(10)

• Hamiltonian cycles and 1-factors in 5-regular graphs
• Homomorphisms of partial \(t\)-trees and edge-colorings of partial 3-trees
• Homomorphisms of signed graphs
• Packing six \(T\)-joins in plane graphs
• Graph edge coloring: a survey
• Edge-colouring seven-regular planar graphs
• Homomorphism bounds and edge-colourings of \(K_{4}\)-minor-free graphs
• Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs
• Walk-powers and homomorphism bounds of planar signed graphs
• A survey on flows in graphs and matroids

This page was built for publication: Edge-colouring eight-regular planar graphs

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