Chromatické číslo

z Wikipédie, slobodnej encyklopédie
Skočit na navigaci Skočit na vyhledávání

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 .

Vlastnosti[upraviť | upraviť kód]

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

Pozri aj[upraviť | upraviť kód]