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 t-edge connected r-regular graphs. The focus is on studying the relationship between edge-connectivity and the existence of regular factors.