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]

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

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