Kromatično število

Iz Wikipedije, proste enciklopedije
Jump to navigation Jump to search
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[1]) grafa G je v teoriji grafov najmanjše število k, za katerega 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[uredi | uredi kodo]

Viri[uredi | uredi kodo]