STUDENT Seminar
PROGRAM
Plan rada Studentskog seminara za JANUAR 2025.
Petak, 17.01.2025. u 12:30, sala 301f, Kneza Mihaila 36 i
On-line
Strahinja Gvozdić, ETH Cirih
NAJLAKŠE JE SAVRŠEN GRAF OBOJITI
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.
Predavanja su namenjena širokom krugu slušalaca. Održavaju se petkom sa početkom u 12:00 sati u sali 301f na trećem spratu zgrade Matematičkog instituta SANU, Knez Mihailova 36.
Luka Milićević
Rukovodilac seminara
Ivana Đurđev Brković
Sekretar seminara