A 3-edge-coloring of the Desargues graph. En matematisk graf (eller nätverk) är en naturlig modell för en mängd vitt skilda fenomen inom naturvetenskap, teknik och datavetenskap där man studerar parvisa relationer mellan objekt, från konkreta exempel som en karta över vägar och kemiska molekyler till sociala nätverk och kommunikation mellan datorer i ett nätverk.
Idén att använda grafer som matematiska modeller tillskrivs vanligen den schweiziska matematikern Euler och dennes lösning av det berömda problemet med broarna i Königsberg, men det var det likaledes berömda fyrfärgsproblemet - Kan varje karta färgläggas med fyra olika färger så att länder med gemensam gräns får olika färger? - som var drivande bakom att grafteori under 1900-talet utvecklades till en självständig matematisk disciplin. I dagens moderna grafteori finns beröringspunkter med de flesta andra matematiska inriktningar, men mycket av forskningen i grafteori är även fortsatt starkt problemorienterad.
Forskargruppen i grafteori vid LiU studerar framför allt klassisk grafteori med ett särskilt fokus på graffärgningar och Hamiltonsk grafteori. Inom Hamiltonsk grafteori undersöker vi framför allt lokala villkor för Hamiltoncykler eller långa cykler i grafer.
Vi arbetar med många olika graffärgningsvarianter med en särskild tonvikt på kantfärgningar. Mycket av forskningen handlar också om listfärgningar, där vi undersöker både deterministiska och probabilistiska modeller.
Vi har flera nationella och internationella forskningssamarbeten och välkomnar regelbundet gäster till forskargruppen.
