Extending partial 3-colourings in a planar graph

Matt DeVos; Paul Seymour

doi:10.1016/S0095-8956(02)00005-9

Extending partial 3-colourings in a planar graph

Matt DeVos, Paul Seymour

Mathematics

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

7 Scopus citations

Abstract

Let D be a disc, and let X be a finite subset of points on the boundary of D. An essential part of the proof of the four colour theorem is the fact that many sets of 4-colourings of X do not arise from the proper 4-colourings of any graph drawn in D. In contrast to this, we show that every set of 3-colourings of X arises from the proper 3-colourings of some graph drawn in D.

Original language	English (US)
Pages (from-to)	219-225
Number of pages	7
Journal	Journal of Combinatorial Theory. Series B
Volume	88
Issue number	2
DOIs	https://doi.org/10.1016/S0095-8956(02)00005-9
State	Published - Jul 2003

All Science Journal Classification (ASJC) codes

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics

Access to Document

10.1016/S0095-8956(02)00005-9

Cite this

@article{1004bea641db41988668aa384ec5b78c,

title = "Extending partial 3-colourings in a planar graph",

abstract = "Let D be a disc, and let X be a finite subset of points on the boundary of D. An essential part of the proof of the four colour theorem is the fact that many sets of 4-colourings of X do not arise from the proper 4-colourings of any graph drawn in D. In contrast to this, we show that every set of 3-colourings of X arises from the proper 3-colourings of some graph drawn in D.",

author = "Matt DeVos and Paul Seymour",

year = "2003",

month = jul,

doi = "10.1016/S0095-8956(02)00005-9",

language = "English (US)",

volume = "88",

pages = "219--225",

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

issn = "0095-8956",

publisher = "Academic Press Inc.",

number = "2",

}

TY - JOUR

T1 - Extending partial 3-colourings in a planar graph

AU - DeVos, Matt

AU - Seymour, Paul

PY - 2003/7

Y1 - 2003/7

N2 - Let D be a disc, and let X be a finite subset of points on the boundary of D. An essential part of the proof of the four colour theorem is the fact that many sets of 4-colourings of X do not arise from the proper 4-colourings of any graph drawn in D. In contrast to this, we show that every set of 3-colourings of X arises from the proper 3-colourings of some graph drawn in D.

AB - Let D be a disc, and let X be a finite subset of points on the boundary of D. An essential part of the proof of the four colour theorem is the fact that many sets of 4-colourings of X do not arise from the proper 4-colourings of any graph drawn in D. In contrast to this, we show that every set of 3-colourings of X arises from the proper 3-colourings of some graph drawn in D.

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

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

U2 - 10.1016/S0095-8956(02)00005-9

DO - 10.1016/S0095-8956(02)00005-9

M3 - Article

AN - SCOPUS:0038688019

SN - 0095-8956

VL - 88

SP - 219

EP - 225

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

IS - 2

ER -

Extending partial 3-colourings in a planar graph

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this