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 $\chi (G)$.

Vlastnosti

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

Pozri aj

• farbenie grafov