Cesko.wiki Barvení grafu
Author
Albert FloresObarvený graf - 3 barvy Petersenova grafu jsou obarvitelné třemi barvami
Barvení grafu je jednou z disciplín teorie grafů, která se zabývá přiřazováním barev (téměř vždy reprezentovaných přirozenými čísly) různým objektům v grafu - vrcholům, hranám, stěnám atd. Nejčastěji jde o barvení vrcholů, ostatní případy (jako např. +more barvení sousedících ploch) lze na tento jednoduše převést.
Definice
Nechť G = (V, E) je graf, k přirozené číslo. Zobrazení b: V\rarr\{1, 2, \ldots, k \} nazveme obarvením grafu G pomocí k barev, pokud pro každou hranu \{x, y\}\in E platí b(x)\neq b(y). +more Barevnost grafu (také chromatické číslo) G je minimální počet barev potřebný pro obarvení G. Značí se \chi (G).
Některé vlastnosti \chi (G)
# \chi (G) = 1 právě tehdy, skládá-li se G z izolovaných vrcholů (diskrétní graf) # \chi (G) = |V| pro libovolný úplný graf # \chi (G)\ge 3 právě tehdy, obsahuje-li G kružnici liché délky (ekvivalentně, není-li G bipartitní) # \chi (G)\le 4 pro libovolný rovinný graf (viz slavný problém čtyř barev) # \chi (G)\le \Delta(G) + 1 (maximální stupeň vrcholu v grafu + 1)
