Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5777671 | Journal of Combinatorial Theory, Series B | 2017 | 19 Pages |
Abstract
A classical result of Birkhoff and Lewis implies that every planar graph with n vertices has at least 15â
2nâ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.
Keywords
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Carsten Thomassen,