<p>This paper: <a href="http://www.mimuw.edu.pl/~kowalik/papers/grotzsch-full.pdf">http://www.mimuw.edu.pl/~kowalik/papers/grotzsch-full.pdf</a>
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.</p>

<p>I'm not exactly sure, but does this answer your question?</p>

CC BY-SA 3.0
2014-03-05T05:33:20.333Z
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
CC BY-SA 3.0
2014-03-05T05:36:26.240Z
Well, if we allow triangles then it won't necessarily be 3-colourable (?)
JimN
CC BY-SA 3.0
2014-03-05T05:44:36.963Z
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
CC BY-SA 3.0
2015-11-19T08:09:36.377Z
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
CC BY-SA 3.0
2014-03-05T04:53:22.587Z
2014-03-05T04:53:22.587Z
JimN
<p>The <a href="http://en.wikipedia.org/wiki/Four_color_theorem" rel="nofollow noreferrer">four-color theorem</a> claims that, any loopless planar graph is 4-colorable. However, it is NP-Complete to determine the chromatic number of planar graphs, <a href="http://www.sciencedirect.com/science/article/pii/0012365X80902368" rel="nofollow noreferrer">even for those 4-regular ones</a>.</p>

<p><a href="http://en.wikipedia.org/wiki/Girth_%28graph_theory%29" rel="nofollow noreferrer">Girth</a> is the length of the smallest cycle in a graph. Planar graph with girth at least 4, i.e., triangle-free, is 3-colorable, <a href="http://www.sciencedirect.com/science/article/pii/S0095895684710690" rel="nofollow noreferrer">shown in paper</a>. </p>

<p><strong>Question:</strong>
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?</p>

<p>I find another post "<a href="https://cstheory.stackexchange.com/questions/489/graph-families-which-have-polynomial-time-algorithms-for-computing-the-chromatic?rq=1">graph families which have polynomial algorithms for chromatic number</a>" might be related.</p>

CC BY-SA 3.0
2014-03-05T02:15:19.570Z
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
CC BY-SA 3.0
2014-03-05T02:36:52.263Z
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
CC BY-SA 3.0
2014-03-05T02:43:35.997Z
@YonatanN Thanks. I edited the question. I want to find such a 3-coloring.
Peng Zhang
<cc.complexity-theory><graph-theory><graph-colouring><planar-graphs>
Chromatic number of planar graph with girth at least k
Peng Zhang
# Chromatic number of planar graph with girth at least k

(Asked by: username_0 on 2014-03-05)

The [four-color theorem](http://en.wikipedia.org/wiki/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](http://www.sciencedirect.com/science/article/pii/0012365X80902368).

[Girth](http://en.wikipedia.org/wiki/Girth_%28graph_theory%29) 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](http://www.sciencedirect.com/science/article/pii/S0095895684710690).

**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](https://cstheory.stackexchange.com/questions/489/graph-families-which-have-polynomial-time-algorithms-for-computing-the-chromatic?rq=1)" might be related.

**Tags:** cc.complexity-theory, graph-theory, graph-colouring, planar-graphs

> **Comments:**
> **username_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).  
> **username_1**: 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.  
> **username_0**: @YonatanN Thanks. I edited the question. I want to find such a 3-coloring.  

---

## 1 answers

### Answer by username_2 on 2014-03-05. Score: 7 | Accepted answer

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?

> **Comments:**
> **username_0**: 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?  
> **username_2**: Well, if we allow triangles then it won't necessarily be 3-colourable (?)  
> **username_0**: 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.  
> **username_3**: 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  

---

