Kritičan graf
Izgled
![](http://upload.wikimedia.org/wikipedia/commons/thumb/a/a8/Critical_graph_sample.svg/250px-Critical_graph_sample.svg.png)
Kritičan graf je onaj graf za koji vrijedi[1]:1
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 -kromatski, onda ga nazivamo -kritičnim. Svaki graf kromatskog broja ima kritičan podgraf kromatskog broja -kromatski.[1]:1 Za minimalni stupanj -kritičnog grafa vrijedi da je[1]:2
Izvori[uredi | uredi kôd]
- ↑ a b c Odjel za matematiku Sveučilišta u Rijeci Ana Jurasić: Bojenje grafova (pristupljeno 3. listopada 2020.)