Naredni sastanak Seminara biće održan u petak, 17. januara 2024. godine u sali 301f Matematičkog instituta SANU sa početkom u 12.30 časova.
 
Predavač: Strahinja Gvozdić, ETH Cirih

Naslov predavanja: NAJLAKŠE JE SAVRŠEN GRAF OBOJITI

Apstrakt:
Graf G nazivamo savršenim ukoliko u svakom njegovom indukovanom podgrafu H važi χ(H)=ω(H), gde su sa χ i ω označeni, redom, hromatski broj i najveća klika u N. Pojam je prvi uveo Berž 1961. kada je i postavio dve čuvene hipoteze o strukturi savršenih grafova koje su u međuvremenu dokazane i danas su poznate pod nazivom slaba, odnosno jaka, teorema o savršenim grafovima. Prva hipoteza tvrdi da je komplement svakog savršenog grafa takođe savršen, dok druga daje potpunu strukturalnu karakterizaciju savršenih grafova kao grafova koji ne sadrže indukovane neparne cikluse dužine veće od 3 niti komplemente istih. Na predavanju ćemo dati dokaz slabe teoreme o savršenim grafovima, predstaviti glavne ideje dokaza jake teoreme o savršenim grafovima i objasniti kako se efikasno (u polinomijalnom vremenu) može izračunati hromatski broj savršenog grafa.

Napomena: Predavanja se mogu pratiti na daljinu preko linka:
https://miteam.mi.sanu.ac.rs/call/CihYM6Nratzix7c8G/uJmcdEJs4INWQ8MEoLVzHRGxbfbBEWSBMwXBYcymVoj

Registraciona forma je dostupna na:
https://miteam.mi.sanu.ac.rs/asset/M4zcEwxkzy5PqNS73