Bojenje grafa

Bojenje grafova. Bojenje grafa je funkcija , pri čemu je konačan skup boja sa svojstvom:[1]

Bojenje je -bojenje ako je .[1]

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 .[1]

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

VidiUredi

IzvoriUredi

  1. a b c d Prirodoslovno-matematički fakultet u ZagrebuInačica izvorne stranice arhivirana 25. svibnja 2020. Tomislav Bujanović: Grafovi i njihova svojstva (pristupljeno 26. svibnja 2020.)

Vanjske povezniceUredi