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 .

Vlastnosti[upraviť | upraviť zdroj]

  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ť zdroj]