Graph Theory

The research group in graph theory at Linköping University is primarily interested in classic graph theory with a particular focus on graph coloring and Hamiltonian graph theory.

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. A mathematical graph (or network) is a natural model for a wide variety of phenomena and processes in the natural and social sciences, as well as in information and computer science, for studying pairwise relations between objects, including natural examples such as a road network or bonds in chemical molecules to more abstract phenomena such as links in social networks or data communication in a computer nework.

The idea of using graphs as mathematical models is usually attributed to the Swiss mathematician Euler and his well-known solution of the famous Königsberg bridge problem, but it was the equally famous Four color problem - Can every map be colored with four colors so that neighboring countries get different colors? - which was the driving force behind the fact that graph theory evolved into a mathematical discipline in its own right in the 20th century. In today's modern graph theory, there are connections to most other mathematical subjects; nevertheless, much of the research in graph theory remains strongly problem-oriented.

The research group in graph theory at Linköping University is primarily interested in classic graph theory with a particular focus on graph coloring and Hamiltonian graph theory.

In Hamiltonian graph theory we are primarily intersted in local conditions for Hamilton cycles or long cycles in graphs.

We study several graph coloring variants with a particular emphasis on edge colorings. A lot of the research is also devoted to questions on list coloring, where we investigate both deterministic and probabilistic models.

We collaborate with several other research groups and regularly welcome guests to the research group.

Members of the research group Graph Theory

New publications

2024

Carl Johan Casselgren, Fikre B. Petros, Samuel A. Fufa (2024) Extending partial edge colorings of Cartesian products of graphs Discussiones Mathematicae. Graph Theory Continue to DOI
Carl Johan Casselgren, Mesfin Masre (2024) Extremal values on the general degree-eccentricity index of trees of fixed maximum degree AUSTRALASIAN JOURNAL OF COMBINATORICS, Vol. 88, p. 212-220

2023

Carl Johan Casselgren (2023) Brooks' theorem with forbidden colors Journal of Graph Theory Continue to 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, p. 25-35 Continue to 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, p. 139-153 Continue to DOI

2022

Carl Johan Casselgren, Fikre B. Petros (2022) Edge Precoloring Extension of Trees II Discussiones Mathematicae. Graph Theory Continue to DOI
Armen Asratian, Jonas Granholm (2022) On Hamiltonicity of regular graphs with bounded second neighborhoods Discrete Applied Mathematics, Vol. 316, p. 75-86 Continue to 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, p. 2080-2116 Continue to DOI
Carl Johan Casselgren, Per Johansson, Klas Markström (2022) Avoiding and Extending Partial Edge Colorings of Hypercubes Graphs and Combinatorics, Vol. 38, Article 79 Continue to DOI
Carl Johan Casselgren (2022) Anote on one-sided interval edge colorings of bipartite graphs Discrete Mathematics, Vol. 345, Article 112690 Continue to DOI

Organisation