Factors in graphs
Final Report Abstract
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 properly color the edges of a simple graph with maximum vertex degree k is equal to k or to k + 1. This result divides the class of simple graphs into two classes; a graph is in class 1 if it is edge colorable with k colors and in class 2 otherwise. For neither class there are characterizations and it is an N P -complete problem to decide whether a graph is colorable with k colors. Little is known about the structure of graphs of class 2. In addition to the study of factors in edge-chromatic critical graphs the investigation of rgraphs of class 2 was a major focus of the project. Many hard graph-theoretical problems can be reduced to r-graphs. Every r-graph has a perfect matching and every r-edge colorable r-graph contains r pairwise disjoint perfect matchings. Thus, the set of r-graphs can be partitioned into sets Rk (k ∈ {1, · · · , r}), where G ∈ Rk , if k is the maximum number of pairwise disjoint perfect matchings in G. Among other things, the relationship between edge-connectivity and the existence of pairwise disjoint perfect matchings was investigated. Let m(t, r) be the maximum number s such that every t-edge connected r-graph contains s pairwise disjoint perfect matchings. We have proved upper bounds for this parameter, which indicate that r-graphs with only a few pairwise disjoint perfect matchings have small edge connectivity. The concept of H-coloring for r-graphs is a unifying approach for studying questions on matchings and cycles in r-graphs. This concept was first introduced by Jaeger (1985) for cubic graphs. Let Hr be an inclusion-wise minimal set of r-graphs such that for every r-graph G there is a graph H ∈ Hr that colors G. Jaeger conjectured that H3 only contains the Petersen graph. This conjecture is open and we consider the question of whether Hr is a finite set. We show that this can only be the case if r = 3 and Jaeger’s conjecture is true.
Link to the final report
https://oa.tib.eu/renate/handle/123456789/19760
Publications
-
Some conjectures on r-graphs and equivalences
Y. Ma, E. Steffen, I. H. Wolf & J. Zhang
-
Even Factors in Edge-Chromatic-Critical Graphs with a Small Number of Divalent Vertices. Graphs and Combinatorics, 38(3).
Steffen, Eckhard & Wolf, Isaak H.
-
Bounds for the chromatic index of signed multigraphs. Discrete Applied Mathematics, 337, 185-189.
Steffen, Eckhard & Wolf, Isaak H.
-
Edge-Connectivity and Pairwise Disjoint Perfect Matchings in Regular Graphs. Combinatorica, 44(2), 429-440.
Ma, Yulai; Mattiolo, Davide; Steffen, Eckhard & Wolf, Isaak H.
-
Pairwise Disjoint Perfect Matchings in r-Edge-Connected r-Regular Graphs. SIAM Journal on Discrete Mathematics, 37(3), 1548-1565.
Ma, Yulai; Mattiolo, Davide; Steffen, Eckhard & Wolf, Isaak H.
-
Rotation r-graphs. Discrete Mathematics, 113457.
Steffen, Eckhard & Wolf, Isaak H.
-
Cubic graphs with edges in precisely one perfect matching
J. Goedgebeur, D. Mattiolo, G. Mazzuoccolo, J. Renders & I. H. Wolf
-
Factors in graphs, Dissertation, Faculty for Electrical Engineering, Computer Science, and Mathematics (Institute for Mathematics), Paderborn University, August 2024
I.H. Wolf
-
Fractional factors and component factors in graphs with isolated toughness smaller than 1. Journal of Graph Theory, 108(2), 274-287.
Wolf, Isaak H.
-
On the existence of factors intersecting sets of cycles in regular graphs
J. Goedgebeur, D. Mattiolo, G. Mazzuoccolo, J. Renders, L. Toffanetti & I. H. Wolf
-
Reconfiguration Graphs for Vertex Colorings of P5-Free Graphs. Annals of Applied Mathematics, 40(4), 394-411.
Lei, Hui; Ma, Yulai; Miao, Zhengke; Shi, Yongtang & Wang, Susu
-
Sets of r-Graphs that Color All r-Graphs. Combinatorica, 45(2).
Ma, Yulai; Mattiolo, Davide; Steffen, Eckhard & Wolf, Isaak H.
