Chromatic number of planar graph with girth at least k
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?