Grafteori

Forskargruppen i grafteori vid LiU studerar framför allt klassisk grafteori med ett särskilt fokus på graffärgningar och Hamiltonsk grafteori.

A 3-edge-coloring of the Desargues graph. Created by: Koko90. CC BY-SA 3.0. https://en.wikipedia.org/wiki/Edge_coloring#/media/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.

Medlemmar i forskargruppen Grafteori

Nya publikationer

2023

Carl Johan Casselgren (2023) Brooks' theorem with forbidden colors Journal of Graph Theory Vidare till DOI
Armen Asratian, Carl Johan Casselgren, Petros A. Petrosyan (2023) Decomposing graphs into interval colorable subgraphs and no-wait multi-stage schedules Discrete Applied Mathematics, Vol. 335, s. 25-35 Vidare till DOI
Carl Johan Casselgren, Herman Göransson (2023) Completing partial Latin squares with two filled rows and three filled columns Journal of Combinatorics, Vol. 14, s. 139-153 Vidare till DOI

2022

Carl Johan Casselgren, Fikre B. Petros (2022) Edge Precoloring Extension of Trees II Discussiones Mathematicae. Graph Theory Vidare till DOI
Armen Asratian, Jonas Granholm (2022) On Hamiltonicity of regular graphs with bounded second neighborhoods Discrete Applied Mathematics, Vol. 316, s. 75-86 Vidare till DOI
Kai Hoppmann-Baum, Oleg Burdakov, Gioni Mexi, Carl Johan Casselgren, Thorsten Koch (2022) Length-constrained cycle partition with an application to UAV routing* Optimization Methods and Software, Vol. 37, s. 2080-2116 Vidare till DOI
Carl Johan Casselgren, Per Johansson, Klas Markström (2022) Avoiding and Extending Partial Edge Colorings of Hypercubes Graphs and Combinatorics, Vol. 38, Artikel 79 Vidare till DOI
Carl Johan Casselgren (2022) Anote on one-sided interval edge colorings of bipartite graphs Discrete Mathematics, Vol. 345, Artikel 112690 Vidare till DOI

2021

Carl Johan Casselgren, Jonas Granholm, A. Raspaud (2021) A note on adaptable choosability and choosability with separation of planar graphs Journal of Combinatorial Mathematics and Combinatorial Computing, Vol. 116, s. 101-109
Carl Johan Casselgren, Jonas Granholm, Andre Raspaud (2021) On star edge colorings of bipartite and subcubic graphs Discrete Applied Mathematics, Vol. 298 Vidare till DOI

Organisation