thumb|right|200px|Zgled barvanja Petersenovega grafa po točkah. Za njegovo barvanje so potrebne tri različne barve, njegovo kromatično število pa je enako 3. Kromatično število (ali barvnost) grafa G je v teoriji grafov najmanjše število k, za katero je G k-pobarvljiv, oziroma je najmanjše število barv, s katerimi je mogoče pobarvati graf G po točkah tako, da imajo pari točk poljubne povezave različne barve. Običajno se označuje kot .
Sklici
Viri
Kategorija:Teorija grafov Kategorija:NP-polni problemi Kategorija:Invariante grafov