Kromatski broj

Graf se može 3-obojiti na 12 načina

Kromatski broj grafa $\gamma (G)$ je najmanji prirodan broj $k$ sa svojstvom da je $G$ $k$-obojiv. Ako je $\gamma (G)=k$ tada je graf $G$ $k$-kromatski odnosno $k$-obojiv.

Kod kritičnih grafova vrijedi da su povezani, a da nije tako 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.

Često nije jednostavno točno odrediti kromatski, ali postoje relativno dobre gornje i donje međe te razne druge ograde kromatskog broja. Na točno određivanje kromatskog broja svode se mnogi kombinatorni problemi, među kojima je problem četiri boje, primjeri Hadwigerove slutnje i dr.

Vidi

• Subdivizija brida
• Subdivizija grafa
• Graf inkompatibilnosti

Vanjske poveznice

• Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku Iva Gregurić: Bojenje grafova, Osijek, 2011.