Számítástudományi és Információelméleti Tanszék

A kromatikus szám az egyik legtöbbet vizsgált gráfparaméter. Irodalma óriási, viselkedése egyes helyzetekben ismert, másokban teljesen megértetlen. A rokon paraméterek száma is nagyon nagy.

A jelen témakiírásra jelentkezôk elsô számú feladata a hatalmas irodalom valamely olyan szeletének (támavezetôi segítséggel történô) kiválasztása, melyet szívesen áttekintenek, majd ezen belül közösen kiválasztott nyitott problémákon való gondolkodás.

Példa a gráfszínezéseken belüli részterületre a következô. Gráfoknak sokféle szorzatát szokás definiálni, s ha a gráfot többször önmagával szorozzuk, az eredményt a gráf hatványának hívjuk. A különbözô szorzások illetve hatványozások által létrejövô gráfok kromatikus számának értéke rendszerint szoros kapcsolatban van az összeszorzott gráfok kromatikus számának értékével. Ezt a kapcsolatot esetenként szép tételek, máskor csak bizonyítatlan sejtések fejezik ki. Ha az ismert sejtések túl nehezek is, a témakör áttekintése talán új, az ismerteknél könnyebben kezelhetô sejtésekre, jó esetben azok igazolására vezethet.

Egy másik nagy terület a gráfszínezések témakörén belül a perfekt gráfok témaköre. Az idetartozó korábbi vizsgálatok többnyire két híres nemrégiben megoldott probléma, az ún. Erôs Perfekt Gráf Sejtés (2002 óta: Erôs Perfekt Gráf Tétel, mely azt mondja ki, hogy egy gráf pontosan akkor perfekt, ha sem ô sem a komplementere nem tartalmaz feszített részgráfként legalább öt hosszú páratlan kört) és a perfekt gráfok polinomidôben való felismerhetôségének kérdése köré szervezôdnek. Az e két kitüntetett kérdés megválaszolásáig vezetô út sz\'amos próbálkozása és bizonyos egyéb algoritmikus eredmények a perfekt gráfokat a gráfelmélet egyik központi fogalmává tették, kiterjedt elméletükben sok további máig megoldatlan kérdést is megfogalmaztak. E kérdések és eredmények bôs\'eges alkalmat adhatnak mind a nyitott kérdéseken való gondolkozásra, mind a tanulásra.

Irodalom:

Szükséges nyelvtudás: angol.

Dr. Simonyi Gábor
egyetemi docens
31-56
simonyi@renyi.hu