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

  • $\begingroup$ 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? $\endgroup$ – Oleksandr Bondarenko Nov 22 '10 at 17:47
  • $\begingroup$ The table entry refers to Robertson, Sanders, Seymour, and Thomas Four Coloring paper which deals with Bridgeless cubic planar graphs. $\endgroup$ – Mohammad Al-Turkistany Nov 22 '10 at 18:13
  • $\begingroup$ +1 great question, I'm have a simliar, but more practical one... $\endgroup$ – 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.

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


  • $\begingroup$ 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>. $\endgroup$ – RJK Oct 31 '10 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.