Prof. Dr. Eckhard Steffen

PI, start September 2024

Many important questions in graph theory (such as the 5-flow conjecture or the cycle double cover conjecture) can be reduced to the class of cubic graphs. In fact, it suffices to solve them for bridgeless cubic graphs that do not admit a 3-edge coloring, the so-called snarks. Due to their importance, the study of snarks is a very active area of research in graph theory. Many of the problems reducible to snarks have natural generalizations for r-regular graphs with r>3, so that in recent years this class of graphs has become an increasing focus of mathematical research. In the project, these graphs are studied in order to gain new insights into the interaction of methods and properties between the r=3 case and the general case. This is done with reference to the finer classification of r-regular graphs (r>3) with respect to pairwise disjoint perfect matchings, which does not exist for cubic graphs.

P.I., start Januar 2024 (5 Years)
Scientific Research Network, FWO (Belgium)

The scientific research network consists of the following working groups: Jan De Beule (Vrije Universiteit Brussel); Kris Coolsaet, Leo Storm (Universiteit Gent); Jan Goedgebeur (KU Leuven); Aida Abaid (Eindhoven University of Technology); Karen Aardal (TU Delft); Eric Opdam (University of Amsterdam); Eckhard Steffen (Paderborn University)

P.I., Project duration 01/2020 - 12/2024
DFG - Deutsche Forschungsgemeinschaft

Edge coloring and factors of graphs are classical areas of graph theory. Early and fundamental theorems of graph theory, such as König's theorem (1916) or Petersen's theorem (1891) make statements about edge colorings and factors of graphs. Factors of regular graphs are of particular interest. Vizing (1965) showed that the minimum number of colors, which are needed to color the edges of a simple graph with maximum vertex degree k properly is equal to k or to k+1. This results divides the class of simple graphs into two classes; a graph is class 1 if it is edge colorable with k colors and class 2 otherwise. For neither class there are characterizations and it is an NP-complete problem to decide whether a graph is colorable with k colors, even for 3-regular graphs (Holyer 1981). Little is known about the structure of class 2 graphs. One goal of the proposed research project is to gain new insights into the structure of critical graphs. Based on the result that every critical class 2 graph has specific [1,2]-factors, the methods shall be further developed to approximate Vizing’s critical graph conjectures. Findings from the study of critical graphs shall be further used to prove statements about factors of r-graphs, especially of planar r-graphs, and also of t-edge connected r-regular graphs. The focus is on studying the relationship between edge-connectivity and the existence of regular factors.