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.

  1. 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.
  2. 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.
  3. 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