Matematické Fórum

Lucien · 17. 12. 2011 16:07

Ahoj, chtěl bych se ujistit, jestli jsem něco nepřehlédl. Mám příklad:

Nechť G je netriviální regulární graf se sudým počtem vrcholů. Dokažte, že $\psi _{e}(G) = \Delta(G) + 1$ .

$\psi _{e}(G)$ je minimální počet barev potřebný k hranovému obarvení grafu G.
$\Delta(G)$ je minimální stupeň grafu G.

Podle mého toto nelze dokázat, ale vyvrátit. Mohu sestrojit graf, který toto tvrzení vyvrací.
Například:

Pro výše uvedený graf platí, že $\Delta(G)$ = 2 a $\psi _{e}(G)$ = 2.

Je můj úsudek správný a nepřehlédl jsem něco? Předem děkuji za odpověď.

petrkovar · 17. 12. 2011 18:26

Ano,uvedené tvrzení neplatí. Ale platí jiné tvrzení: "Nechť G je netriviální regulární graf s lichým počtem vrcholů. Dokažte, že $\chi _{e}(G) = \Delta(G) + 1$ ".

Lucien · 17. 12. 2011 22:41

↑ petrkovar:
Děkuji, moc jste mi pomohl.

Matematické Fórum

#1 17. 12. 2011 16:07

Hranové barvení grafu

#2 17. 12. 2011 18:26

Re: Hranové barvení grafu

#3 17. 12. 2011 22:41

Re: Hranové barvení grafu

Zápatí