Kritičan graf

Datoteka:Critical graph sample.svg

Primjeri kritičkih grafova

Kritičan graf je onaj graf za koji vrijedi

$\gamma (G-v)<\gamma (G),\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. Za minimalni stupanj $\delta (G)$ $k$-kritičnog grafa $G$ vrijedi da je

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