For which values of $k$ can all planar graphs of girth $k$ be coloured with less than or equal to 3 colours?

74 Views Asked by At

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!

1

There are 1 best solutions below

0
On

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.