16
$\begingroup$

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

Improve this question
$\endgroup$
4

3 Answers 3

Reset to default
17
$\begingroup$

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.

Improve this answer
$\endgroup$
4
  • 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
    Commented Feb 22, 2011 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
    Commented May 5, 2011 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
    Commented Jul 10, 2011 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
    Commented Dec 1, 2018 at 15:45
5
$\begingroup$

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

Improve this answer
$\endgroup$
4
$\begingroup$

You might find this paper of interest:

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

Improve this answer
$\endgroup$
1
  • 1
    $\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
    Commented Oct 31, 2010 at 15:42

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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