Barvení grafu
Z Wikipedie, otevřené encyklopedie
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 lze na tento jednoduše převést.
[editovat] Definice
Nechť G = (V, E) je graf, k přirozené číslo. Zobrazení 
nazveme obarvením grafu G pomocí k barev, pokud pro každou hranu 
platí 
. Barevnost grafu (také chromatické číslo G je minimální počet barev potřebný pro obarvení G. Značí se χ(G).
[editovat] Některé vlastnosti χ(G)
- χ(G) = 1 právě tehdy, skládá-li se G z izolovaných vrcholů
právě tehdy, obsahuje-li G kružnici liché délky (ekvivaletně, není-li G bipartitní)
pro libovolný rovinný graf (viz slavný problém čtyř barev)
