Odeljenje za matematiku, 16. mart 2018.

Naredni sastanak Seminara biće održan u petak, 16. marta 2018. u sali 301f Matematičkog instituta SANU sa početkom u 14:15 časova.

Predavač: Bojan Vučković, Matematički fakultet, Univerzitet u Beogradu

Naslov predavanja: INDUKOVANA BOJENjA GRAFOVA

Apstrakt: 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.



Nažalost nije moguće ostaviti komentar.