Kromatski broj

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.^[1]^:1

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.^[1]^:1

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

Vidi

Izvori

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

Vanjske poveznice

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

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

[1]