The number of colorings of planar graphs with no separating triangles
详细信息 查看全文
- 作者：Carsten Thomassen1 ; ctho@dtu.dk
- 关键词：Chromatic polynomial ; Planar triangulations
- 刊名：Journal of Combinatorial Theory, Series B
- 出版年：2017
- 出版时间：January 2017
- 年：2017
- 卷：122
- 期：Complete
- 页码：615-633
- 全文大小：425 K
- 卷排序：122
文摘
A classical result of Birkhoff and Lewis implies that every planar graph with n vertices has at least 15⋅2n−115⋅2n−1 distinct 5-vertex-colorings. Equality holds for planar triangulations with n−4n−4 separating triangles. We show that, if a planar graph has no separating triangle, then it has at least (2+10−12)n(2+10−12)n distinct 5-vertex-colorings. A similar result holds for k -colorings for each fixed k≥5k≥5. Infinitely many planar graphs without separating triangles have less than 2.252n2.252n distinct 5-vertex-colorings. As an auxiliary result we provide a complete description of the infinite 6-regular planar triangulations.