Kromatski broj – Hrvatska internetska enciklopedija

# Kromatski broj

Izvor: Hrvatska internetska enciklopedija
More actions
Graf se može 3-obojiti na 12 načina

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

- Subdivizija brida
- Subdivizija grafa
- Graf inkompatibilnosti

## Izvori

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.)

## Vanjske poveznice

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

Dobavljeno iz "https://enciklopedija.cc/index.php?title=Kromatski_broj&oldid=383916"