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.

  • 1
    $\begingroup$ 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). $\endgroup$ – Yonatan N Mar 5 '14 at 2:15
  • $\begingroup$ 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. $\endgroup$ – Yonatan N Mar 5 '14 at 2:36
  • 1
    $\begingroup$ @YonatanN Thanks. I edited the question. I want to find such a 3-coloring. $\endgroup$ – Peng Zhang Mar 5 '14 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.

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

  • $\begingroup$ 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? $\endgroup$ – Peng Zhang Mar 5 '14 at 5:33
  • $\begingroup$ Well, if we allow triangles then it won't necessarily be 3-colourable (?) $\endgroup$ – JimN Mar 5 '14 at 5:36
  • 1
    $\begingroup$ 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. $\endgroup$ – Peng Zhang Mar 5 '14 at 5:44
  • 1
    $\begingroup$ 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 $\endgroup$ – Louis Esperet Nov 19 '15 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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