Kritičan graf
Kritičan graf je onaj graf za koji vrijedi [1]:1
[math]\displaystyle{ \gamma (G-v) \lt \gamma (G) , \forall v \in V (G) }[/math]
Kritični grafovi su povezani, inače bi svaka komponenta povezanosti imala isti kromatski broj kao čitav graf. Vrijedi li da je kritičan graf [math]\displaystyle{ G }[/math] [math]\displaystyle{ k }[/math]-kromatski, onda ga nazivamo [math]\displaystyle{ k }[/math]-kritičnim. Svaki graf kromatskog broja [math]\displaystyle{ k }[/math] ima kritičan podgraf kromatskog broja [math]\displaystyle{ k }[/math]-kromatski.[1]:1 Za minimalni stupanj [math]\displaystyle{ \delta (G) }[/math] [math]\displaystyle{ k }[/math]-kritičnog grafa [math]\displaystyle{ G }[/math] vrijedi da je [1]:2
[math]\displaystyle{ \delta (G) \geq k-1 }[/math]
Izvori
- ↑ 1,0 1,1 1,2 Odjel za matematiku Sveučilišta u Rijeci Ana Jurasić: Bojenje grafova (pristupljeno 3. listopada 2020.)