Faktoren in Graphen

• Antragsteller: Professor Dr. Eckhard Steffen
• Fachliche Zuordnung: Mathematik
• Förderung: Förderung von 2020 bis 2024
• Projektkennung: Deutsche Forschungsgemeinschaft (DFG) - Projektnummer 445863039

• Erstellungsjahr: 2025

Zusammenfassung der Projektergebnisse

Kantenfärbungen und Faktoren von Graphen sind klassische Gebiete der Graphentheorie. Frühe und die Graphentheorie prägende Sätze, wie z.B. der Satz von König (1916) oder der Satz von Petersen (1891) machen Aussagen über Kantenfärbungen und Faktoren von Graphen. Besonderes Interesse gilt Faktoren von regulären Graphen. Vizing (1965) zeigte, dass die minimale Anzahl von Farben, mit denen die Kanten eines einfachen Graphen mit maximalem Eckengrad k gefärbt werden können entweder gleich k oder k + 1 ist. Das Ergebnis teilt die Klasse der einfachen Graphen in zwei Klassen ein; G ist in Klasse 1, falls G k-kantenfärbbar ist und andernfalls in Klasse 2. Für keine der beiden Klassen gibt es Charakterisierungen und es ist ein N P -vollständiges Problem zu entscheiden, ob ein Graph mit k Farben färbbar ist. Es ist wenig über die Struktur von Graphen der Klasse 2 bekannt. Neben dem Studium von Faktoren in kantenfärbungskritischen Graphen bildete die Untersuchung von r-Graphen der Klasse 2 einen wesentlichen Schwerpunkt des Projektes. Jeder r-Graph hat ein perfektes Matching und jeder r-kantenfärbbare r-Graph enthält r paarweise disjunkte perfekte Matchings. Somit lässt sich die Menge der r-Graphen in Mengen Rk (k ∈ {1, · · · , r}) partitionieren, wobei G ∈ Rk , falls k die maximale Anzahl paarweise disjunkter perfekter Matchings in G ist. Es wurde u.a. das Verhältnis zwischen Kantenzusammenhang und der Existenz von paarweise disjunkten perfekten Matchings untersucht. Sei m(t, r) die maximale Zahl s, so dass jeder tkantenzusammenhängende r-Graph s paarweise disjunkte perfekte Matchings enthält. Wir haben obere Schranken für diesen Parameter bewiesen, die darauf hinweisen, dass r-Graphen mit nur wenigen paarweise disjunkten perfekten Matchings einen kleinen Kantenzusammenhang haben. Das Konzept der H-Färbung für r-Graphen ist ein vereinheitlichender Ansatz zur Untersuchung von Fragen zu Zyklen und Matchings in r-Graphen. Dieses Konzept wurde von Jaeger (1985) zunächst für kubische Graphen eingeführt. Sei Hr eine minimale Menge von r-Graphen, so dass es für jeden r-Graphen G einen Graphen H ∈ Hr gibt, der G färbt. Jaeger vermutete, dass H3 nur den Petersengraphen enthält. Diese Vermutung ist offen, und wir betrachten die Frage, ob Hr eine endliche Menge ist. Wir zeigen, dass dies nur dann der Fall ist, falls r = 3 und Jaegers Vermutung wahr ist.

Link zum Abschlussbericht

https://oa.tib.eu/renate/handle/123456789/19760

Projektbezogene Publikationen (Auswahl)

• 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.