Kritičan graf

Primjeri kritičkih grafova

Kritičan graf je onaj graf za koji vrijediPredložak:Is

$\gamma (G-v)<\gamma (G),\mathrm{\forall }v\in V(G)$

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 $G$ $k$-kromatski, onda ga nazivamo $k$-kritičnim. Svaki graf kromatskog broja $k$ ima kritičan podgraf kromatskog broja $k$-kromatski.Predložak:Is Za minimalni stupanj $\delta (G)$ $k$-kritičnog grafa $G$ vrijedi da jePredložak:Is

$\delta (G)\ge k-1$