Seminar Katedre za računarstvo i informatiku, 8. mart 2018.

Naredni sastanak Seminara biće održan u četvrtak, 8. marta 2018. u sali 718 Matematičkog fakulteta sa početkom u 18:15 časova.

Predavač: Bojan Vučković

Naslov predavanja: INDUKOVANA BOJENjA GRAFOVA

Apstrakt: Bojenje grafova podrazumeva dodelu boja čvorovima, granama, ili čvorovima i granama grafa. Uobičajeni uslov ovakvog bojenja je da se susednim čvorovima, incidentnim granama, odnosno čvorovima i njima incidentnim granama, dodeljuju različite boje. Ovakva bojenja se nazivaju valjanim, i glavno pitanje koje se razmatra 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 unapređivanje.



Nažalost nije moguće ostaviti komentar.