Take the 2-minute tour ×
Theoretical Computer Science Stack Exchange is a question and answer site for theoretical computer scientists and researchers in related fields. It's 100% free, no registration required.

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

Edit Feb 22, 2011: Cross posted on Math Overflow.

share|improve this question
    
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
add comment

3 Answers

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.

share|improve this answer
5  
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
1  
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
add comment

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

share|improve this answer
add comment

You might find this paper of interest:

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

share|improve this answer
    
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
add comment

Your Answer

 
discard

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.