5

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.

Community
  • 1
Peng Zhang
  • 1,453
  • 9
  • 19
  • 1
    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 05 '14 at 02: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 05 '14 at 02:36
  • 1
    @YonatanN Thanks. I edited the question. I want to find such a 3-coloring. – Peng Zhang Mar 05 '14 at 02:43

1 Answers1

7

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?

JimN
  • 1,316
  • 6
  • 13
  • 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 05 '14 at 05:33
  • Well, if we allow triangles then it won't necessarily be 3-colourable (?) – JimN Mar 05 '14 at 05:36
  • 1
    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 05 '14 at 05:44
  • 1
    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 – Louis Esperet Nov 19 '15 at 08:09