The square of a planar cubic graph is 7-colorable

Carsten Thomassen

doi:10.1016/j.jctb.2017.08.010

The square of a planar cubic graph is 7-colorable

Carsten Thomassen

Department of Applied Mathematics and Computer Science

Research output: Contribution to journal › Journal article › Research › peer-review

293 Downloads (Orbit)

Abstract

We prove the conjecture made by G. Wegner in 1977 that the square of every planar, cubic graph is 7-colorable. Here, 7 cannot be replaced by 6.

Original language	English
Journal	Journal of Combinatorial Theory. Series B
Volume	128
Pages (from-to)	192-218
ISSN	0095-8956
DOIs	https://doi.org/10.1016/j.jctb.2017.08.010
Publication status	Published - 2017

Keywords

Theoretical Computer Science
Discrete Mathematics and Combinatorics
Computational Theory and Mathematics
Chromatic number
Square of graph

Access to Document

10.1016/j.jctb.2017.08.010

5Accepted author manuscript, 287 KBLicence: CC BY-NC-ND

OpenUrl availability

Full text

Cite this

@article{d33433a74d474b628d3475dc3b53ff58,

title = "The square of a planar cubic graph is 7-colorable",

abstract = "We prove the conjecture made by G. Wegner in 1977 that the square of every planar, cubic graph is 7-colorable. Here, 7 cannot be replaced by 6.",

keywords = "Theoretical Computer Science, Discrete Mathematics and Combinatorics, Computational Theory and Mathematics, Chromatic number, Square of graph",

author = "Carsten Thomassen",

year = "2017",

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

language = "English",

volume = "128",

pages = "192--218",

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

issn = "0095-8956",

publisher = "Academic Press",

}

TY - JOUR

T1 - The square of a planar cubic graph is 7-colorable

AU - Thomassen, Carsten

PY - 2017

Y1 - 2017

N2 - We prove the conjecture made by G. Wegner in 1977 that the square of every planar, cubic graph is 7-colorable. Here, 7 cannot be replaced by 6.

AB - We prove the conjecture made by G. Wegner in 1977 that the square of every planar, cubic graph is 7-colorable. Here, 7 cannot be replaced by 6.

KW - Theoretical Computer Science

KW - Discrete Mathematics and Combinatorics

KW - Computational Theory and Mathematics

KW - Chromatic number

KW - Square of graph

U2 - 10.1016/j.jctb.2017.08.010

DO - 10.1016/j.jctb.2017.08.010

M3 - Journal article

SN - 0095-8956

VL - 128

SP - 192

EP - 218

JO - Journal of Combinatorial Theory. Series B

JF - Journal of Combinatorial Theory. Series B

ER -

The square of a planar cubic graph is 7-colorable

Abstract

Keywords

Access to Document

OpenUrl availability

Fingerprint

Cite this