A gráfok színezésével kapcsolatos legalapvetőbb mennyiség a kromatikus szám. Ez az egyik legtöbbet vizsgált gráfparaméter, a vele kapcsolatos tételeknek se szeri se száma. Miközben sok mindent tudunk a kromatikus számról, még több az, amit nem tudunk. Számos évtizedek óta nyitott kérdés (Erdős-Faber-Lovász sejtés, Reed sejtés, Hedetniemi sejtés) megoldatlan. Rengeteg kromatikus szám típusú egyéb paraméter is felbukkant az elmúlt években, évtizedekben, melyek újabb kérdéseket vetnek fel e rokon paraméterek viselkedésével kapcsolatban. Tipikusan a feladat ezek megbecslése különféle gráfosztályokon, illetve annak tisztázása, hogy az új paraméter milyen viszonyban van a kromatikus számmal, mennyire térhet el attól.
A téma művelése során a fenti típusú kérdésekre keresünk választ.
Ideális esetben a téma iránt érdeklődő hallgató már TDK dolgozat vagy diplomamunka készítés keretében ilyen paraméterekkel foglalkozott, és doktori tanulmányai alatt a már így megkezdett munkát folytathatja.
előírt nyelvtudás: angol felvehető hallgatók száma: 1
Jelentkezési határidő: 2018-01-31
2024. IV. 17. ODT ülés Az ODT következő ülésére 2024. június 14-én, pénteken 10.00 órakor kerül sor a Semmelweis Egyetem Szenátusi termében (Bp. Üllői út 26. I. emelet).
Bejelentkezés
