Bojenje grafa

Bojenje grafova. Bojenje grafa $G=(V,E)$ je funkcija $f:V\rightarrow S$ , pri čemu je $S$ konačan skup boja sa svojstvom:^[1] $(u,v)\in E\implies f(u)\neq f(v).$

Bojenje je $k$ -bojenje ako je $|Im(f)|=k$ . ^[1]

Graf $G=(V,E)$ je $k$ -obojiv ako postoji $1$ -bojenje grafa za neki $l\leq k$ . Ako je $G$ $k$ -obojiv, a nije $k-1$ -obojiv, kažemo da je $G$ $k$ -kromatski. Za $k$ kažemo da je kromatski broj te ga označavamo se $\chi (G)$ .^[1]

Ciklički graf može se obojiti samo na dva načina, dok bojenje Petersenovog grafa nije jedinstveno. ^[1]

Vidi

Izvori

↑ ^1,0 ^1,1 ^1,2 ^1,3 Prirodoslovno-matematički fakultet u Zagrebu Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)

Vanjske poveznice

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

[Bujanović-1] 1,0 ^1,1 ^1,2 ^1,3 Prirodoslovno-matematički fakultet u Zagrebu Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)

[1]