Kromatično število: razlika med redakcijama

dodanih 775 zlogov ,  pred 2 letoma
m
m+/dp
(N)
 
m (m+/dp)
 
[[slika:Petersen graph 3-coloring.svg|thumb|right|200px|Zgled [[barvanje grafa|barvanja]] [[Petersenov graf|Petersenovega grafa]] po [[točka (teorija grafov)|točkah]]. Za njegovo barvanje so potrebne tri različne barve, njegovo kromatično število pa je enako 3.]]
'''Kromatično število''' (ali '''barvnost'''<ref name="wilson_1997" />) [[graf (matematika)|grafa]] ''G'' je v [[teorija grafov|teoriji grafov]] najmanjše število ''k'', za katerega je ''G'' [[k-pobarvljivi graf|''k''-pobarvljiv]], oziroma je najmanjše število barv, s katerimi je mogoče [[barvanje grafa|pobarvati]] graf ''G'' po [[točka (teorija grafov)|točkah]] tako, da imajo pari točk poljubne [[povezava (teorija grafov)|povezave]] različne barve. Običajno se označuje kot <math> \chi (G) \!\, </math>.
 
<gallery>
11-simplex graph.svg|Kromatično število vsakega [[polni graf|polnega grafa]] <math> K_{n} \!\, </math> pri <math> n\ge 2 \!\, </math> je <math>n \!\, </math>. Na sliki polni graf <math> K_{12} \!\, </math>
Hypercubestar.svg|Kromatično število [[hiperkockin graf|hiperkockinega grafa]] je 2
DesarguesGraph.svg|Kromatično število [[Desarguesov graf|Desarguesovega grafa]] je 2
Ljubljana graph hamiltonian.svg|Kromatično število [[Ljubljanski graf|Ljubljanskega grafa]] je 2
Frucht graph.neato.svg|Kromatično število [[Fruchtov graf|Fruchtovega grafa]] je 3
Biggs-Smith graph.svg|Kromatično število [[Biggs-Smithov graf|Biggs-Smithovega grafa]] je 3
Higman Sims Graph.svg|Kromatično število [[Higman-Simsov graf|Higman-Simsovega grafa]] je 6
</gallery>
 
== Sklici ==