Bojenje grafa

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

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

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

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

Vidi

• Bojenje vrhova (teorija grafova)
• Bojenje bridova (teorija bridova)
• Problem četiriju boja

Izvori

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

Vanjske poveznice

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