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.
Login
