National Institute of the Republic of Serbia
ὅδε οἶκος, ὦ ἑταῖρε, μνημεῖον ἐστιν ζωῶν τῶν σοφῶν ἀνδρῶν, καὶ τῶν ἔργων αὐτῶν
PROGRAM
| ODELJENJE ZA MATEMATIKU MATEMATIČKOG INSTITUTA SANU |
PROGRAM ZA MART 2018.
PETAK, 16.03.2018. u 14:15, Sala 301f, MI SANU, Kneza Mihaila 36
Bojan Vučković, Matematički fakultet, Beograd
INDUKOVANA BOJENJA GRAFOVA
Bojenje grafa podrazumeva dodelu boja čvorovima, granama, ili čvorovima i
granama grafa. Uobičajeni uslov kod ovih bojenja je da se susednim
čvorovima, incidentnim granama, odnosno čvorovima i njima incidentnim
granama, dodeljuju različite boje. Ovakva bojenja nazivaju se valjanim, i
najviše izučavani problem je koji je minimalan broja boja potrebnih da bi se
takvo bojenje izvelo.
Pored valjanih bojenja, poslednjih decenija postoji značajno interesovanje
za indukovana bojenja grafova. To su ne obavezno valjana bojenja kod kojih
se boja čvora izvodi iz boja njemu incidentnih grana. Bojenja se najčešće
izvode po sumi ili po skupu, pri čemu se postavlja uslov da svaka dva
susedna čvora, ili generalno svaka dva čvora grafa, imaju različite izvedene
vrednosti.
Na izlaganju će biti prikazane definicije raznih vrsta indukovanog bojenja
grafa, kao i hipoteze po pitanju potrebnog broja boja da bi se izvelo
traženo bojenje za proizvoljan graf. Kod mnogih od ovih tipova bojenja
postignuti rezultati su još uvek daleko od pretpostavljenih gornjih granica
datih u hipotezama i ostavljaju prostora za dalje unapređivanje.