250px|mini|desno|Graf se može 3-obojiti na 12 načina Kromatski broj grafa je najmanji prirodan broj sa svojstvom da je -obojiv. Ako je tada je graf -kromatski odnosno -obojiv.Odjel za matematiku Sveučilišta u Rijeci Ana Jurasić: Bojenje grafova (pristupljeno 3. listopada 2020.)
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 -kromatski, onda ga nazivamo -kritičnim. Svaki graf kromatskog broja ima kritičan podgraf kromatskog broja -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
Izvori
Vanjske poveznice Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku Iva Gregurić: Bojenje grafova, Osijek, 2011.
Kategorija:Teorija grafova