Barvení grafu: Porovnání verzí
Smazaný obsah Přidaný obsah
→Některé vlastnosti \chi (G): chromatické číslo je menší nebo rovnu maximálnímu stupni vrcholu v grafu |
Bez shrnutí editace |
||
Řádek 12:
# <math>\chi (G)\ge 3</math> právě tehdy, obsahuje-li G [[kružnice (graf)|kružnici]] liché délky (ekvivaletně, není-li G [[bipartitní graf|bipartitní]])
# <math>\chi (G)\le 4</math> pro libovolný [[rovinný graf]] (viz slavný [[problém čtyř barev]])
# <math>\chi (G)\le \delta_{max} + 1</math> maximální stupeň uzlu v grafu + 1
[[Kategorie:Grafové pojmy]]
| |||