Thesis supervisor: Gábor Simonyi
Location of studies (in Hungarian): BME VIK SZIT Abbreviation of location of studies: BME
Description of the research topic:
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.
Required language skills: angol Number of students who can be accepted: 1