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$

1 Answer 1

4
$\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$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .