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

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

• farbenie grafov

Tento článok týkajúci sa matematiky je zatiaľ „výhonok“. Pomôž Wikipédii tým, že ho doplníš a rozšíriš.