5
$\begingroup$

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.

Improve this question
$\endgroup$
3
  • 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
    Commented Mar 5, 2014 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
    Commented Mar 5, 2014 at 2:36
  • 1
    $\begingroup$ @YonatanN Thanks. I edited the question. I want to find such a 3-coloring. $\endgroup$
    – Peng Zhang
    Commented Mar 5, 2014 at 2:43

1 Answer 1

Reset to default
7
$\begingroup$

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?

Improve this answer
$\endgroup$
4
  • $\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
    Commented Mar 5, 2014 at 5:33
  • $\begingroup$ Well, if we allow triangles then it won't necessarily be 3-colourable (?) $\endgroup$
    – JimN
    Commented Mar 5, 2014 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
    Commented Mar 5, 2014 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
    Commented Nov 19, 2015 at 8:09

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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