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.
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.

I'm not exactly sure, but does this answer your question?