# Chromatic number of planar graph with girth at least k

The four-color theorem claims that, any loopless planar graph is 4-colorable. However, it is NP-Complete to determine the chromatic number of planar graphs, even for those 4-regular ones.

Girth is the length of the smallest cycle in a graph. Planar graph with girth at least 4, i.e., triangle-free, is 3-colorable, shown in paper.

Question: Is it NP-Complete to find a 3-coloring of a planar graph with girth at least $k$, where $k$ is a fixed integer? Is there any result about this topic?

I find another post "graph families which have polynomial algorithms for chromatic number" might be related.

• I don't understand the question. Determining whether or not a graph is $2$-colorable is trivial, so it's only interesting when we want to determine whether the chromatic number is $3$ or $4$. You already said it can't be anything bigger than $3$ when $k \geq 4$, answering that case. If $k \leq 3$, this is the general problem on planar graphs and is, as you stated, NP-hard (the decision version being NP-complete). Commented Mar 5, 2014 at 2:15
• my comment says that the problem is linear-time solvable for $k=10$ (or any $k \geq 4$), meaning that it's almost certainly not NP-hard! In those cases, a graph (with at least one edge) has chromatic number 3 iff it doesn't have chromatic number 2. Commented Mar 5, 2014 at 2:36
• @YonatanN Thanks. I edited the question. I want to find such a 3-coloring. Commented Mar 5, 2014 at 2:43

This paper: http://www.mimuw.edu.pl/~kowalik/papers/grotzsch-full.pdf gives an $O(n\log{n})$-time 3-colouring algorithm for triangle-free planar graphs, improving on Thomassen's $O(n^2)$-time constructive proof.

• What if the graph does have triangles, but not squares? For example, a planar of girth at least 5, or 6, ... Will larger girth on planar graph makes the 3-coloring algorithm easier or harder? Commented Mar 5, 2014 at 5:33
• Well, if we allow triangles then it won't necessarily be 3-colourable (?)
– JimN
Commented Mar 5, 2014 at 5:36
• No. I made a mistake of the definition of girth. A girth 4 graph cannot have triangle. Thus, whatever girth k it is, as long as k>=4, we can solve it in O(n*logn). Thanks. Commented Mar 5, 2014 at 5:44
• The complexity of finding a 3-coloring in a triangle-free planar graph is actually known to be linear. See Z. Dvořák, D. Kráľ, R. Thomas: Coloring triangle-free graphs on surfaces, Proceedings of 20th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA'09), pp. 120-129, ACM&SIAM, 2009 Commented Nov 19, 2015 at 8:09