Bipartite are Vizing class I

Task number: 4063

Prove that every bipartite graph \( G \) is of Vizing class I.

  • Hint

    To be sure, let us recall that Vizing class I. means that the edge chromatic number of \( G \) is equal to its maximum degree (\( \chi (L (G)) = \Delta (G) \)). Use matchings.

  • Solution

    Convert the graph to \( \Delta (G) \)-regular bipartite graph \( G’ \) by adding edges and any other vertices. In \( G’ \) we find \( \Delta (G) \) edge disjoint perfect matchings (using Hall’s theorem). We assign a color to each matching and color the edges of \( G’ \) and thus the edges of \( G \), because \( G \) is a subgraph of \( G’ \).

Difficulty level: Easy task (using definitions and simple reasoning)
Proving or derivation task
Cs translation
Send comment on task by email