2012/10/27 by Maria Chudnovsky, Katherine Edwards, Chudnovsky, Maria +5 · 1 citation
Engineering · #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #graph theory and CDMA systems
paper · pdf · doi:10.48550/arxiv.1210.7349
openalex publication_date 2012/10/27 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A conjecture due to the fourth author states that every d-regular planar multigraph 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 d≤ 8, by various authors. In particular, two of us proved it when d=7; and then three of us proved it when d=8. The methods used for the latter give a proof in the d=7 case that is simpler than the original, and we present it here.