Description
A disszertáció a gráfelmélet színezési és információelméleti paramétereinek vizsgálatával foglalkozik, különös tekintettel azokra, amelyek gráfhomomorfizmusokon keresztül univerzális gráfosztályokkal írhatók le. Az első téziscsoport középpontjában a multikromatikus és a frakcionális kromatikus számok állnak, főként a Hedetniemi-sejtéshez kapcsolódó kérdések motivációjából. A dolgozat az úgynevezett szélesen színezhető gráfokra ad pontos eredményeket és becsléseket e paraméterekre, valamint ezek alkalmazásaként felső korlátot határoz meg az ilyen gráfokkal modellezhető csatornák Shannon-kapacitására.
A második téziscsoportban a Kneser- és Schrijver-gráfok színezési paramétereinek vizsgálata során olyan részgráfok azonosítása történik, amelyek a frakcionális kromatikus számra nézve kritikusak. Kimutatásra kerül, hogy a Schrijver-gráfok egy természetes módon definiálható feszített részgráfja csúcskritikus erre a paraméterre, és hogy ez a részgráf izomorf a cirkuláris teljes gráfokkal, amelyek a cirkuláris kromatikus szám univerzális gráfjai. Ennek következtében a cirkuláris teljes gráfok csúcs- és élkritikus tulajdonságai is elemzésre kerülnek mind a frakcionális, mind a cirkuláris kromatikus szám szempontjából.
A harmadik téziscsoport az információelmélethez kapcsolódik: a klasszikus kódtávolság-probléma gráfelméleti általánosításaként olyan gráfcsaládok maximális méreteinek meghatározása történik, amelyekben bármely két gráf szimmetrikus differenciája előírt lokális vagy globális tulajdonságokat elégít ki.