The square of a planar cubic graph is 7-colorable

Research output: Contribution to journalJournal articleResearchpeer-review

187 Downloads (Pure)

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 languageEnglish
JournalJournal of Combinatorial Theory. Series B
Volume128
Pages (from-to)192-218
ISSN0095-8956
DOIs
Publication statusPublished - 2017

Keywords

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

Fingerprint

Dive into the research topics of 'The square of a planar cubic graph is 7-colorable'. Together they form a unique fingerprint.

Cite this