Die Untersuchung der Färbbarkeit mithilfe der Fractional Graph Theory

Inhaltsverzeichnis

• • Aufbau der Arbeit
  • Grundlagen und Definitionen
    • Graphentheorie
    • Stochastik
• Hypergraphen
  • Kantenüberdeckungen
  • Knotenpackungen.
• Matchings
  • Fraktionale Matchings
  • Allgemeines
  • Fraktionales Hamiltonkreisproblem
  • Das duale Problem
• Färbbarkeit
  • Fraktionale Färbbarkeit
  • Allgemeines
  • Das duale Problem
• Reed'sche Vermutung
  • Reed'sche Vermutung im fraktionalen Fall
    • Das Lemma
    • Folgerungen aus Lemma 5.2
    • Vorüberlegungen zum Algorithmus
    • Der Algorithmus
    • Der Beweis
  • Lokale Verschärfung
    • Lokale Version von Lemma 5.2.
    • Lokale Version von Gleichung (4)
    • Der veränderte Algorithmus
    • Der angepasste Beweis

Zielsetzung und Themenschwerpunkte

Die Arbeit untersucht das Konzept der Fractional Graph Theory und erweitert bestehende (ganzzahlige) Konzepte der Graphentheorie auf reelle Werte. Dabei wird der Fokus auf die Anwendung dieser fraktionalen Ansätze auf verschiedene graphentheoretische Probleme wie Matchings und Färbbarkeit gelegt.

• Einführung und Definition der Fractional Graph Theory
• Anwendungen der Fractional Graph Theory auf Hypergraphen
• Untersuchung von fraktionalen Matchings und deren Eigenschaften
• Anwendung der Fractional Graph Theory auf das Problem der Färbbarkeit
• Beweis einer fraktionalen Version der Reed'schen Vermutung

Zusammenfassung der Kapitel

• Kapitel 1 liefert eine Einführung in die Fractional Graph Theory und beleuchtet die grundlegenden Konzepte aus der Graphentheorie und Stochastik, die in der Arbeit verwendet werden.
• Kapitel 2 untersucht fraktionale Werte für die Kantenüberdeckungszahl und die Knotenpackungszahl im Kontext von Hypergraphen.
• Kapitel 3 beschäftigt sich mit Matchings in Graphen und stellt die Konzepte der fraktionalen Matchings und des Hamiltonkreisproblems vor.
• Kapitel 4 behandelt das Thema der Färbbarkeit in Graphen und stellt die fraktionale Färbbarkeit sowie das dazugehörige duale Problem vor.
• Kapitel 5 konzentriert sich auf die Reed'sche Vermutung und bietet einen Beweis für eine fraktionale Version dieser Vermutung sowie für eine noch verschärftere lokale Variante.

Schlüsselwörter

Fraktionale Graphentheorie, Graphentheorie, Hypergraphen, Matchings, Färbbarkeit, chromatische Zahl, Reed'sche Vermutung, lineare Programmierung, Subadditivitäts-Lemma.