# 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? 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. Nov 22 '10 at 18:13
• +1 great question, I'm have a simliar, but more practical one... Nov 20 '13 at 21:30
• Hi, do you know if there is any progress for 3-edge colorings on cubic graphs on a double torus? Jul 30 '19 at 20:24

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 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. 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. 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. 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