A Differenciálegyenletek Tanszék kiírt témái
Gráfokon a színezés kiterjesztések aktuális elméleti és gyakorlati kérdései
Témavezető:Hujter Mihály, egyetemi docens
Napjainkra a gráfok klasszikus színezései kiterjesztésinek kérdésköre több szempontból is fontossá vált.
- Thomassen híres, 1994-es eredményével kapcsolatban új, elméleti vizsgálatok kezdődtek a térképszínezési négy- és öt-szín tételekkel kapcsolatban.
- Algoritmus komplexitási szempontból előtérbe kerültek azok a kérdések, hogy mely feladatváltozatokra tudunk hatékony algoritmusokat szerkeszteni, és melyekre látjuk a problémák NP-teljességét, továbbá mi a helyzet a köztes esetekkel.
- Különösen ütemezési és számítógépes memóriaallokálási gyakorlati kérdéseknél is felhasználásra kerülnek gráfok színezésinek kiterjesztésére vonatkozó fogalmak, tételek és algoritmusok.
A diplomamunka készítőjének feladata lesz a rendkívül széles, gyorsan bővülő szakirodalom áttekintése, alkalmasint egy-egy új eredménnyel, egyszerűsítéssel, észrevétellel való kiegészítése.
Teljesen új, önálló eredmény is üdvözlendő! A hallgató kiindulhat a következő helyekről:
Irodalom:
- [1]
- D. R. Wood and S. Linusson, Thomassen's choosability argument revisited,
arXiv:1005.5194v3
- [2]
- M. Hujter, A large bibliography
- [3]
- R. Diestel. Graph theory, vol. 173 of Graduate Texts in Mathematics. Springer, 3rd edn., 2005.
- [4]
- Graph Coloring and Applications