Tárgyfelelős: Dr. Tuza Zsolt egyetemi tanár
Feltételezett előismeretek:
- Algebra és diszkrét matematika
- Digitális számítások elmélete
- Kombinatorikus módszerek és algoritmusok
- Lineáris programozás
Tematika:
- Gráfok színezéseinek néhány típusa, azokhoz tartozó paraméterek, alapvető egyenlőtlenségek, klasszikus felső korlátok, konstrukciók;
- Kapcsolat fokszámokkal, függetlenségi számmal; kromatikus polinom; kompaktsági elv végtelen gráfokra;
- Színezési problémák algoritmikus komplexitása, approximálhatóság, redukciók színezési típusok között;
- Irányításokhoz kapcsolódó módszerek, algoritmusok és gráfpolinomok;
- Perfekt gráfok néhány fontos osztálya, Perfekt gráf tétel, felfújási lemma, karakterizációk; színezések kiterjeszthetősége perfekt részosztályokon;
- Síkgráfok különféle típusú színezései, algoritmusok; a sík egységtávolságú színezései;
- Frakcionális színezések, többszörös színezések, kiválaszthatósági arány.
Irodalom:
Bodlaender H. L. A tourist guide through treewidth. Acta Cybernetica 11 (1993), 1–21.
Brandstädt A., Le V. B., Spinrad J. P. Graph Classes: A Survey. SIAM Monographs on Discrete Mathematics and Applications, 1999.
Golumbic M. Algorithmic Graph Theory and Perfect Graphs. 2nd ed. Annals of Discrete Mathematics Vol. 57, Elsevier, 2004.
Jensen T. R., Toft B. Graph Coloring Problems. Wiley Interscience, 1995.
Ngo H. Q. Introduction to graph coloring. Online jegyzet: http://www.cse.buffalo.edu/~hungngo/classes/2004/594/notes/Coloring-intro.pdf
Tuza Zs., Graph colorings with local constraints – A survey. Discuss. Math. Graph Theory 17 (1997), 161–228.