Kromatski broj

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

Kromatski broj grafa [math]\displaystyle{ \gamma (G) }[/math] je najmanji prirodan broj [math]\displaystyle{ k }[/math] sa svojstvom da je [math]\displaystyle{ G }[/math] [math]\displaystyle{ k }[/math]-obojiv. Ako je [math]\displaystyle{ \gamma (G) = k }[/math] tada je graf [math]\displaystyle{ G }[/math] [math]\displaystyle{ k }[/math]-kromatski odnosno [math]\displaystyle{ k }[/math]-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 [math]\displaystyle{ G }[/math] [math]\displaystyle{ k }[/math]-kromatski, onda ga nazivamo [math]\displaystyle{ k }[/math]-kritičnim. Svaki graf kromatskog broja [math]\displaystyle{ k }[/math] ima kritičan podgraf kromatskog broja [math]\displaystyle{ k }[/math]-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.