Bejelentkezés
 Fórum
 
 
Témakiírás
 
Simonyi Gábor
Gráfok színezései

TÉMAKIÍRÁS

Intézmény: Budapesti Műszaki és Gazdaságtudományi Egyetem
informatikai tudományok
Informatikai Tudományok Doktori Iskola

témavezető: Simonyi Gábor


A kutatási téma leírása:

A kromatikus szám az egyik legtöbbet vizsgált gráfparaméter. Irodalma óriási, viselkedése egyes helyzetekben ismert, másokban megértetlen. A rokon paraméterek száma is igen 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, melyben szívesen elmélyednek, majd ennek áttekintése után 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 áll az összeszorzott gráfok kromatikus számának értékével. Ezt a kapcsolatot esetenként szép tételek fejezik ki, máskor csak bizonyítatlan sejtések ismertek. Utóbbiakkal kapcsolatban részeredmények elérése is érdekes lehet.

A kromatikus szám és különböző változatainak vizsgálatát számos esetben motiválják a gyakorlatból származó, tipikusan valamifele időbeosztás elkészítésével kapcsolatos problémák. Mindemellett, a jelen témakiírás elsősorban olyanoknak szól, akiket ezen kérdések elméleti oldala érdekel, és egy-egy tisztán gráfelméleti problémán önmagáért is szívesen gondolkoznak.

felvehető hallgatók száma: 1

Jelentkezési határidő: 2008-05-20


2017. III. 21.
ODT ülés
Az ODT következő ülésére 2017. május 5-én 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).

 
Minden jog fenntartva © 2007, Országos Doktori Tanács - a doktori adatbázis nyilvántartási száma az adatvédelmi biztosnál: 02003/0001. Program verzió: 1.2343 ( 2017. II. 28. )