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