The number of colorings of planar graphs with no separating triangles

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.