Bipartitní jsou Vizingovy třídy I
Úloha číslo: 3281
Dokažte, že každý bipartitní graf \(G\) je Vizingovy třidy I.
Nápověda
Pro jistotu připomeňme, že Vizingova třída I. znamená, hranová barevnost \(G\) je rovna jeho maximálnímu stupni (\(\chi(L(G)) = \Delta(G)\)). Užijte párování.
Řešení
Graf převedeme na \(\Delta(G)\)-regulární bipartitní graf \(G'\) přidáním hran a případných dalších vrcholů. V \(G'\) nalezneme \(\Delta(G)\) hranově disjunktních perfektních párování (užití Hallovy věty). Každému párování přiřadíme barvu a obarvíme tak hrany \(G'\) a tím i hrany \(G\), neb \(G\) je podgraf \(G'\).