The square of a planar cubic graph is 7-colorable

Research output: Contribution to journalJournal articleResearchpeer-review

219 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

Cite this