<p>You might find this paper of interest:</p>

<p><a href="http://cs.nyu.edu/cole/papers/edge_col.pdf" rel="nofollow">http://cs.nyu.edu/cole/papers/edge_col.pdf</a></p>

CC BY-SA 2.5
2010-10-31T15:42:23.410Z
Alternatively, http://dx.doi.org/10.1007/s00453-007-9044-3
Odd that this is one of the first hits when you google <edge colouring planar graphs>.
RJK
CC BY-SA 2.5
2010-10-31T15:31:44.950Z
2010-10-31T15:31:44.950Z
Joseph Malkevitch
<p>3-edge coloring of triangle-free graphs with maximum degree 3 is also  NP-complete, see 10.1016/S0096-3003(96)00021-5.</p>

CC BY-SA 3.0
2012-12-07T20:54:25.887Z
2012-12-07T20:54:25.887Z
Diamantis Koreas
<p>Every <em>bridgeless</em> planar cubic graph can be 3-edge-colored in quadratic time, as this task is equivalent to four-coloring a planar graph, which can be done in quadratic time. (See Robertson, Sanders, Seymour and Thomas: <a href="http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps">http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps</a> )</p>

<p>EDIT: As Mathieu points out, cubic graphs with bridges are never 3-edge colourable.</p>

CC BY-SA 3.0
2011-05-05T21:18:49.293Z
To be precise, the equivalence between $3$-edge coloration and $4$-coloration stands only for bridgeless cubic _planar_ graphs.
Mathieu Chapelle
CC BY-SA 3.0
2011-07-10T02:29:57.250Z
@Emil, I do not see how it would imply that cubic PLANAR graphs with bridges are never 3-edge colourable.
Mohammad Al-Turkistany
CC BY-SA 4.0
2018-12-01T15:45:36.037Z
@MohammadAl-Turkistany Given two colours a and b in a d-edge-colouring of a d-regular graph (d>=2), the subgraph induced by the edges coloured a or b is a disjoint union of even cycles. From this follows the Parity Lemma: If X is a proper non-empty subset of V(G) and F is the cut induced by X, then for all colours a and b, the parity of the number of edges of X coloured a is equal to the parity of the number of edges of X coloured b.

Ergo, any d-regular graph (d>=2) with a bridge cannot be d-edge-colourable, regardless of being planar or not.
Leandro Zatesko
CC BY-SA 2.5
2011-02-22T19:51:56.027Z
Cubic graphs with a bridge are never 3-edge-colourable. This follows from the "Parity Lemma" for example see the remark beneath Lemma 2.1 in http://www.combinatorics.org/Volume_17/PDF/v17i1r32.pdf
Colin McQuillan
CC BY-SA 3.0
2010-10-31T12:20:56.437Z
2011-07-08T23:00:45.780Z
2011-07-08T23:00:45.780Z
Emil
<p>3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable". </p>

<blockquote>
  <p>What is the complexity of 3-edge coloring of cubic planar graphs?</p>
</blockquote>

<p>Also, It is conjectured that $\Delta$-edge coloring is $NP$-hard for planar graphs with maximum degree $\Delta \in${4,5}.</p>

<blockquote>
  <p>Has any progress been made towards resolving this conjecture?</p>
</blockquote>

<p>Marek Chrobak and Takao Nishizeki. Improved edge-coloring algorithms
for planar graphs. Journal of Algorithms, 11:102-116, 1990</p>

CC BY-SA 2.5
2010-11-22T17:47:05.187Z
Doesn't line 2 in table 1 in http://dx.doi.org/10.1007/s00453-007-9044-3 mean that "3-edge coloring of cubic planar graphs" is polynomially solvable?
Oleksandr Bondarenko
CC BY-SA 2.5
2010-11-22T18:13:39.187Z
The table entry refers to Robertson, Sanders, Seymour, and Thomas Four Coloring paper which deals with _Bridgeless_ cubic planar graphs.
Mohammad Al-Turkistany
CC BY-SA 3.0
2013-11-20T21:30:05.637Z
+1 great question, I'm have a simliar, but more [practical one](http://math.stackexchange.com/q/519455/19341)...
draks ...
CC BY-SA 4.0
2019-07-30T20:24:28.667Z
Hi, do you know if there is any progress for [3-edge colorings on cubic graphs on a double torus](https://mathoverflow.net/q/337280/11856)?
draks ...
<cc.complexity-theory><graph-theory><np-hardness><graph-colouring>
Complexity of edge coloring in planar graphs
Mohammad Al-Turkistany
# Complexity of edge coloring in planar graphs

(Asked by: username_0 on 2010-10-31)

3-edge coloring of cubic graphs is $NP$-complete. Four Color Theorem is equivalent to "Every cubic planar bridgeless graphs is 3-edge colorable".

> What is the complexity of 3-edge coloring of cubic planar graphs?

Also, It is conjectured that $\Delta$-edge coloring is $NP$-hard for planar graphs with maximum degree $\Delta \in${4,5}.

> Has any progress been made towards resolving this conjecture?

Marek Chrobak and Takao Nishizeki. Improved edge-coloring algorithms
for planar graphs. Journal of Algorithms, 11:102-116, 1990

**Tags:** cc.complexity-theory, graph-theory, np-hardness, graph-colouring

> **Comments:**
> **username_1**: Doesn't line 2 in table 1 in http://dx.doi.org/10.1007/s00453-007-9044-3 mean that "3-edge coloring of cubic planar graphs" is polynomially solvable?  
> **username_0**: The table entry refers to Robertson, Sanders, Seymour, and Thomas Four Coloring paper which deals with _Bridgeless_ cubic planar graphs.  
> **username_2**: +1 great question, I'm have a simliar, but more [practical one](http://math.stackexchange.com/q/519455/19341)...  
> **username_2**: Hi, do you know if there is any progress for [3-edge colorings on cubic graphs on a double torus](https://mathoverflow.net/q/337280/11856)?  

---

## 3 answers

### Answer by username_6 on 2010-10-31. Score: 17 | Accepted answer

Every *bridgeless* planar cubic graph can be 3-edge-colored in quadratic time, as this task is equivalent to four-coloring a planar graph, which can be done in quadratic time. (See Robertson, Sanders, Seymour and Thomas: <http://people.math.gatech.edu/~thomas/OLDFTP/fcdir/fcstoc.ps> )

EDIT: As Mathieu points out, cubic graphs with bridges are never 3-edge colourable.

> **Comments:**
> **username_9**: Cubic graphs with a bridge are never 3-edge-colourable. This follows from the "Parity Lemma" for example see the remark beneath Lemma 2.1 in http://www.combinatorics.org/Volume_17/PDF/v17i1r32.pdf  
> **username_7**: To be precise, the equivalence between $3$-edge coloration and $4$-coloration stands only for bridgeless cubic _planar_ graphs.  
> **username_0**: @username_6, I do not see how it would imply that cubic PLANAR graphs with bridges are never 3-edge colourable.  
> **username_8**: @MohammadAl-Turkistany Given two colours a and b in a d-edge-colouring of a d-regular graph (d>=2), the subgraph induced by the edges coloured a or b is a disjoint union of even cycles. From this follows the Parity Lemma: If X is a proper non-empty subset of V(G) and F is the cut induced by X, then for all colours a and b, the parity of the number of edges of X coloured a is equal to the parity of the number of edges of X coloured b.  Ergo, any d-regular graph (d>=2) with a bridge cannot be d-edge-colourable, regardless of being planar or not.  

---

### Answer by username_5 on 2012-12-07. Score: 5

3-edge coloring of triangle-free graphs with maximum degree 3 is also NP-complete, see 10.1016/S0096-3003(96)00021-5.


---

### Answer by username_3 on 2010-10-31. Score: 4

You might find this paper of interest:

<http://cs.nyu.edu/cole/papers/edge_col.pdf>

> **Comments:**
> **username_4**: Alternatively, http://dx.doi.org/10.1007/s00453-007-9044-3 Odd that this is one of the first hits when you google <edge colouring planar graphs>.  

---

