Kromatično število

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

• 
  Kromatično število vsakega polnega grafa $K_n$ pri $n\ge 2$ je $n$. Na sliki polni graf $K_{12}$
• 
  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

Viri

• Predloga:Citat