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

Obtížnost: Snadná úloha (řešená úvahou nebo přímo z definic)
Úloha na dokazování, ověřování
En translation
	Zaslat komentář k úloze