0
$\begingroup$

I am curious, is there an edge-coloring theorem that is equivalent to the famous Four Color Theorem?

In graph-theoretic terminology, the four-color theorem states that the vertices of every planar graph can be colored with at most four colors so that no two adjacent vertices receive the same color, or for short, "every planar graph is four-colorable"

When vertex-coloring is replaced by edge-coloring, is there an equivalent result?

If no such equivalent result exists, is there a “similar” result?

Thanks a lot.

$\endgroup$
3
$\begingroup$

The Wikipedia article Edge coloring states "Bridgeless planar cubic graphs are all of class 1; this is an equivalent form of the four color theorem." The article explains that when the chromatic index of a graph is equal to the maximum degree of any of its vertices, then the graph is defined as class 1.

$\endgroup$

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.