Chromatic index of planar cubic graphs

Task number: 4064

Prove that every planar cubic graph without bridges is of Vizing class I.

  • Hint

    First, color the faces, and only then derive the edge coloring from the face coloring.

  • Solution

    Let us have a planar cubic graph \( G \) without bridges. We want to color its edges using the three colors \( a, b, c \). According to the 4 color theorem, we first color the faces of \( G \) using colors 1,2,3 and 4. Because the graph \( G \) has no bridges, each edge separates different faces.

    The edge gets the color according to the colors of the incident faces. The color \( a \) corresponds to two possible pairs of face colors \( (1{,}2), (3{,}4) \); color \( b \) corresponds to pairs \( (1{,}3), (2{,}4) \) and color \( c \) to pairs \( (1{,}4), (2 , 3) \).

    Every two adjacent edges have exactly one face in common and therefore different colors.

Difficulty level: Hard task
Proving or derivation task
Solution require uncommon idea
Cs translation
Send comment on task by email