The number of proper vertex-3-colorings of every triangle-free planar graph with n vertices and with no separating cycle of length 4 or 5 is at least 2n/17700000. On the other hand, for infinitely many n, there exists a triangle-free planar graph with separating cycles of length 4 and 5 whose number of proper vertex-3-colorings is <215n/log2(n).
Bibliographical noteFunding Information:
Supported by Independent Research Fund Denmark, 8021-002498 AlgoGraph.
© 2021 Elsevier Inc.
- Planar graphs