Chromatické číslo

z Wikipédie, slobodnej encyklopédie
Prejsť na: navigácia, hľadanie

Chromatické číslo grafu alebo farebnosť grafu je minimálny počet farieb, ktoré musíme použiť na zafarbenie vrcholov grafu, ak každá hrana spája vrcholy rôznych farieb. Označuje sa symbolom \chi (G).

Vlastnosti[upraviť | upraviť zdroj]

  1. \chi (G) = 1 práve vtedy, keď sa skladá z izolovaných vrcholov
  2. \chi (G)\ge 3 práve vtedy, keď obsahuje kružnicu nepárnej dĺžky
  3. \chi (G)\le 4 pre ľubovoľný rovinný graf (pozri problém štyroch farieb)

Pozri aj[upraviť | upraviť zdroj]