vpravo|náhled|Obarvený graf – 3 barvy náhled|vpravo|Vrcholy 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ř. 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í 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 .
Některé vlastnosti = 1 právě tehdy, skládá-li se G z izolovaných vrcholů (diskrétní graf) = |V| pro libovolný úplný graf právě tehdy, obsahuje-li G kružnici liché délky (ekvivalentně, není-li G bipartitní) pro libovolný rovinný graf (viz slavný problém čtyř barev) (maximální stupeň vrcholu v grafu + 1)
Externí odkazy
Kategorie:Grafové pojmy Kategorie:NP-úplné problémy