Bojenje grafova. Bojenje grafa je funkcija , pri čemu je konačan skup boja sa svojstvom:
Bojenje je -bojenje ako je .
Graf je -obojiv ako postoji -bojenje grafa za neki . Ako je -obojiv, a nije -obojiv, kažemo da je -kromatski. Za kažemo da je kromatski broj te ga označavamo se .Prirodoslovno-matematički fakultet u Zagrebu Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)
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
Izvori
Vanjske poveznice Sveučilište J. J. Strossmayera u Osijeku - Odjel za matematiku Iva Gregurić: Bojenje grafova, Osijek, 2011.
Kategorija:Teorija grafova