Bruggen bouwen tussen graafkleuring, extremale en structurele grafentheorie

Het doel van dit project is om vooruitgang te maken op en het verbinden van verschillende belangrijke deelgebieden van grafentheorie. 
Hierbij focusen we op 2 onderzoekslijnen, waarbij we extremale voorbeelden zullen bestuderen. 
De hoofdonderzoekslijn gaat over
I. Hadwiger’s vermoeden en gerelateerd
Hadwiger’s vermoeden is een van de belangrijkste vermoedens in grafentheorie. Indien waar, zou het 2 grote deelgebieden, graafkleuring en structurele grafentheorie verbinden. 
In dit project willen we dit vermoeden met andere, minder bestudeerde vermoedens en problemen relateren.
Zo zullen we een vermoeden van Furedi, Gyarfas en Simonyi uit 2005 onderzoeken, gebruikmakend van probabilistische en structurele technieken.
Dit maakt het mogelijk meer inzicht in Hadwiger's vermoeden en gerelateerde problemen te krijgen.
Als tweede onderzoekslijn, zouden we graag een probleem volledig oplossen dat eerder asymptotisch opgelost was door de applicant.
II. Plesnik’s Probleem Precies
Het fundamentele probleem van Plesnik gaat over de meest elementaire concepten van een graaf; orde, diameter en totale afstand.
Het deel van de wiskundige community dat op dit en gerelateerde problemen werkt, is niet volledig tevreden met de asymptotische oplossing en vraagt zich af of een preciezer antwoord mogelijk is.
Wij willen dat probleem oplossen door onder andere een efficient polynomiaal algoritme te construeren die het antwoord en de extremale grafen berekent voor een belangrijk aantal gevallen.