Barvení grafu

(c) Maxx, CC BY-SA 3.0

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í ${\displaystyle b:V\rightarrow \{1,2,\ldots ,k\}}$ nazveme obarvením grafu G pomocí k barev, pokud pro každou hranu ${\displaystyle \{x,y\}\in E}$ platí ${\displaystyle b(x)\neq b(y)}$. Barevnost grafu (také chromatické číslo) G je minimální počet barev potřebný pro obarvení G. Značí se ${\displaystyle \chi (G)}$.

Některé vlastnosti ${\displaystyle \chi (G)}$

1. ${\displaystyle \chi (G)}$ = 1 právě tehdy, skládá-li se G z izolovaných vrcholů (diskrétní graf)
2. ${\displaystyle \chi (G)}$ = |V| pro libovolný úplný graf
3. ${\displaystyle \chi (G)\geq 3}$ právě tehdy, obsahuje-li G kružnici liché délky (ekvivalentně, není-li G bipartitní)
4. ${\displaystyle \chi (G)\leq 4}$ pro libovolný rovinný graf (viz slavný problém čtyř barev)
5. ${\displaystyle \chi (G)\leq \Delta (G)+1}$ (maximální stupeň vrcholu v grafu + 1)

Externí odkazy

• Obrázky, zvuky či videa k tématu Barvení grafu na Wikimedia Commons