Sie haben Javascript deaktiviert!
Sie haben versucht eine Funktion zu nutzen, die nur mit Javascript möglich ist. Um sämtliche Funktionalitäten unserer Internetseite zu nutzen, aktivieren Sie bitte Javascript in Ihrem Browser.

Show image information
Show image information
Show image information
Show image information
Discrete Mathematics / Graph Theory
Prof. Dr. Eckhard Steffen

Factors in graphs

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 r-edge connected r-regular graphs.

The University for the Information Society