Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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.

share|improve this question
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). –  Yonatan N Mar 5 '14 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. –  Yonatan N Mar 5 '14 at 2:36
@YonatanN Thanks. I edited the question. I want to find such a 3-coloring. –  Peng Zhang Mar 5 '14 at 2:43

1 Answer 1

up vote 6 down vote accepted

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?

share|improve this answer
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? –  Peng Zhang Mar 5 '14 at 5:33
Well, if we allow triangles then it won't necessarily be 3-colourable (?) –  Jim Nastos Mar 5 '14 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. –  Peng Zhang Mar 5 '14 at 5:44

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.