Kromatično število
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 .
Kromatično število vsakega polnega grafa pri je . Na sliki polni graf
Kromatično število hiperkockinega grafa je 2
Kromatično število Desarguesovega grafa je 2
Kromatično število Ljubljanskega grafa je 2
Kromatično število Fruchtovega grafa je 3
Kromatično število Biggs-Smithovega grafa je 3
Kromatično število Higman-Simsovega grafa je 6
Sklici[uredi | uredi kodo]
- ↑ Wilson; Watkins (1997), str. 278.
Viri[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