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

↑ ^a ^b ^c ^d Prirodoslovno-matematički fakultet u Zagrebu Arhivirana inačica izvorne stranice od 25. svibnja 2020. (Wayback Machine) 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] Prirodoslovno-matematički fakultet u Zagrebu Arhivirana inačica izvorne stranice od 25. svibnja 2020. (Wayback Machine) Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)

[1]