Let $G_k$ be the family of planar graphs that do not contain cycles of length less than $k$. Determine for which values of $k$ the following statement holds:
For all $G \in G_k$, $\chi(G) \leq 3$.
Any help appreciated, thanks!
Let $G_k$ be the family of planar graphs that do not contain cycles of length less than $k$. Determine for which values of $k$ the following statement holds:
For all $G \in G_k$, $\chi(G) \leq 3$.
Any help appreciated, thanks!
Copyright © 2021 JogjaFile Inc.
Any $k \geq 4$ works, by Grotzsch's Theorem (which states that a triangle-free planar graph is 3-colourable). This is apparently difficult to prove. Showing that $k\geq 6$ is easier, and is proven in this question.