Chromatické číslo

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 
  práve vtedy, keď sa skladá z izolovaných vrcholov
  práve vtedy, keď ide o bipartitný graf
  práve vtedy, keď obsahuje kružnicu nepárnej dĺžky 
  pre ľubovoľný rovinný graf (pozri problém štyroch farieb)

Pozri aj
farbenie grafov

Kategória:Teória grafov