Kritičan graf

Kritičan graf je onaj graf za koji vrijedi ^[1]^:1

$\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.^[1]^:1 Za minimalni stupanj $\delta (G)$ $k$ -kritičnog grafa $G$ vrijedi da je ^[1]^:2

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

Izvori

↑ ^1,0 ^1,1 ^1,2 Odjel za matematiku Sveučilišta u Rijeci Ana Jurasić: Bojenje grafova (pristupljeno 3. listopada 2020.)

[Jurasić-1] 1,0 ^1,1 ^1,2 Odjel za matematiku Sveučilišta u Rijeci Ana Jurasić: Bojenje grafova (pristupljeno 3. listopada 2020.)

[1]