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 d≤7, by various authors. Here we prove it for d=8.
Original language | English (US) |
---|---|
Pages (from-to) | 303-338 |
Number of pages | 36 |
Journal | Journal of Combinatorial Theory. Series B |
Volume | 115 |
DOIs | |
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