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: $(u,v)\in E\implies f(u)\neq f(v).$

Bojenje je $k$-bojenje ako je $|Im(f)|=k$.

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

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

Vidi

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

Vanjske poveznice

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