# Complexity of edge coloring in planar graphs

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

-
Doesn't line 2 in table 1 in dx.doi.org/10.1007/s00453-007-9044-3 mean that "3-edge coloring of cubic planar graphs" is polynomially solvable? – Oleksandr Bondarenko Nov 22 '10 at 17:47
The table entry refers to Robertson, Sanders, Seymour, and Thomas Four Coloring paper which deals with Bridgeless cubic planar graphs. – Mohammad Al-Turkistany Nov 22 '10 at 18:13
+1 great question, I'm have a simliar, but more practical one... – draks ... Nov 20 '13 at 21:30

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.

-
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 combinatorics.org/Volume_17/PDF/v17i1r32.pdf – Colin McQuillan Feb 22 '11 at 19:51
To be precise, the equivalence between $3$-edge coloration and $4$-coloration stands only for bridgeless cubic planar graphs. – Mathieu Chapelle May 5 '11 at 21:18
@Emil, I do not see how it would imply that cubic PLANAR graphs with bridges are never 3-edge colourable. – Mohammad Al-Turkistany Jul 10 '11 at 2:29

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

-

You might find this paper of interest:

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

-
Alternatively, 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 Oct 31 '10 at 15:42