The number of colorings of planar graphs with no separating triangles

Research output: Contribution to journalJournal articleResearchpeer-review

215 Downloads (Pure)

Abstract

A classical result of Birkhoff and Lewis implies that every planar graph with . n vertices has at least . 152n-1 distinct 5-vertex-colorings. Equality holds for planar triangulations with . n-4 separating triangles. We show that, if a planar graph has no separating triangle, then it has at least . (2+10-12)n distinct 5-vertex-colorings. A similar result holds for . k-colorings for each fixed . k≥5. Infinitely many planar graphs without separating triangles have less than . 2.252n distinct 5-vertex-colorings. As an auxiliary result we provide a complete description of the infinite 6-regular planar triangulations.
Original languageEnglish
JournalJournal of Combinatorial Theory. Series B
Volume122
Pages (from-to)615–633
Number of pages19
ISSN0095-8956
DOIs
Publication statusPublished - 2017

Keywords

  • Chromatic polynomial
  • Planar triangulations

Fingerprint

Dive into the research topics of 'The number of colorings of planar graphs with no separating triangles'. Together they form a unique fingerprint.

Cite this