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