# 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

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
• @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 Dec 1 '18 at 15:45

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