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’ \).
