Edge-colouring seven-regular planar graphs

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

doi:10.1016/j.jctb.2014.11.005

Edge-colouring seven-regular planar graphs

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

Mathematics

Research output: Contribution to journal › Article › peer-review

6 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 language	English (US)
Pages (from-to)	276-302
Number of pages	27
Journal	Journal of Combinatorial Theory. Series B
Volume	115
DOIs	https://doi.org/10.1016/j.jctb.2014.11.005
State	Published - 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

Access to Document

10.1016/j.jctb.2014.11.005

Cite this

@article{6177f6722a284b4d8b76e9642d055156,

title = "Edge-colouring seven-regular planar graphs",

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.",

keywords = "Discharging, Edge-colouring, Four colour theorem, Planar graph, Reducible configuration",

author = "Maria Chudnovsky and Katherine Edwards and Kawarabayashi, {Ken ichi} and Paul Seymour",

note = "Publisher Copyright: {\textcopyright} 2015 .",

year = "2015",

month = nov,

day = "1",

doi = "10.1016/j.jctb.2014.11.005",

language = "English (US)",

volume = "115",

pages = "276--302",

journal = "Journal of Combinatorial Theory. Series B",

issn = "0095-8956",

publisher = "Academic Press Inc.",

}

TY - JOUR

T1 - Edge-colouring seven-regular planar graphs

AU - Chudnovsky, Maria

AU - Edwards, Katherine

AU - Kawarabayashi, Ken ichi

AU - Seymour, Paul

PY - 2015/11/1

Y1 - 2015/11/1

N2 - 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.

AB - 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.

KW - Discharging

KW - Edge-colouring

KW - Four colour theorem

KW - Planar graph

KW - Reducible configuration

UR - http://www.scopus.com/inward/record.url?scp=84939253403&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=84939253403&partnerID=8YFLogxK

U2 - 10.1016/j.jctb.2014.11.005

DO - 10.1016/j.jctb.2014.11.005

M3 - Article

AN - SCOPUS:84939253403

SN - 0095-8956

VL - 115

SP - 276

EP - 302

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

Edge-colouring seven-regular planar graphs

Abstract

All Science Journal Classification (ASJC) codes

Keywords

Access to Document

Other files and links

Fingerprint

Cite this