Pojdi na vsebino

Kromatično število

Iz Wikipedije, proste enciklopedije
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]
  • Wilson, Robin James; Watkins, John Jaeger (1997), Uvod v teorijo grafov [Graphs : an introductory approach] (Knjižnica Sigma - 63 izd.), Ljubljana: DFMA Slovenije, COBISS 72250368, ISBN 961-212-081-1