Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Doesn't line 2 in table 1 in 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
up vote 15 down vote accepted

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: )

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

share|cite|improve this answer
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 – 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.

share|cite|improve this answer

You might find this paper of interest:

share|cite|improve this answer
Alternatively, Odd that this is one of the first hits when you google <edge colouring planar graphs>. – RJK Oct 31 '10 at 15:42

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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