Kritičan graf

Izvor: Hrvatska internetska enciklopedija
Skoči na:orijentacija, traži
Primjeri kritičkih grafova

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. 1,0 1,1 1,2 Odjel za matematiku Sveučilišta u Rijeci Ana Jurasić: Bojenje grafova (pristupljeno 3. listopada 2020.)