Edge-colouring seven-regular planar graphs

Maria Chudnovsky, Katherine Edwards, Ken ichi Kawarabayashi, Paul Seymour

Research output: Contribution to journalArticle

5 Scopus citations

Abstract

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.

Original languageEnglish (US)
Pages (from-to)276-302
Number of pages27
JournalJournal of Combinatorial Theory. Series B
Volume115
DOIs
StatePublished - Nov 1 2015

All Science Journal Classification (ASJC) codes

  • Theoretical Computer Science
  • Discrete Mathematics and Combinatorics
  • Computational Theory and Mathematics

Keywords

  • Discharging
  • Edge-colouring
  • Four colour theorem
  • Planar graph
  • Reducible configuration

Fingerprint Dive into the research topics of 'Edge-colouring seven-regular planar graphs'. Together they form a unique fingerprint.

  • Cite this