The number of colorings of planar graphs with no separating triangles

Research output: Contribution to journalJournal articleResearchpeer-review

272 Downloads (Pure)


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
Pages (from-to)615–633
Number of pages19
Publication statusPublished - 2017


  • Chromatic polynomial
  • Planar triangulations


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