Graphentheorie. Zum Beweis von Hadwigers Vermutung für Kantengraphen

Inhaltsverzeichnis

• Einleitung
  • Grundlagen
  • Die Vermutung
• Vorbereitungen
  • Mengers Satz
  • Vizings Adjazenz-Lemma
• Der Beweis für Kantengraphen

Zielsetzung und Themenschwerpunkte

Diese Arbeit beschäftigt sich mit Hadwigers Vermutung in der Graphentheorie. Die Vermutung besagt, dass für jeden einfachen, endlichen Graphen G die chromatische Zahl X(G) größer oder gleich der Anzahl der Knoten im kleinsten vollständigen Graphen Kn ist, der als Minor in G enthalten ist.

• Die chromatische Zahl und ihre Beziehung zur Clique-Zahl
• Hadwigers Vermutung und ihre verschiedenen Beweise
• Die Bedeutung von Kantengraphen und ihre Rolle bei der Verifizierung der Vermutung
• Die verschiedenen Ansätze zur Beweisfindung und die Herausforderungen bei der allgemeinen Gültigkeit
• Wichtige Resultate und Erweiterungen der Vermutung für verschiedene Graphenklassen

Zusammenfassung der Kapitel

Einleitung

Die Arbeit beginnt mit einer Einführung in die grundlegenden Konzepte der Graphentheorie, insbesondere die chromatische Zahl und die Clique-Zahl. Es wird erläutert, wie die Vermutung von Hadwiger entstanden ist und welche Bedeutung sie für die Graphentheorie hat.

Vorbereitungen

Dieses Kapitel führt wichtige Sätze und Lemmata ein, die für den Beweis von Hadwigers Vermutung für Kantengraphen relevant sind. Hierzu gehören Mengers Satz und Vizings Adjazenz-Lemma.

Schlüsselwörter

Die Arbeit konzentriert sich auf die zentralen Themen der Graphentheorie, insbesondere die chromatische Zahl, Clique-Zahl, Hadwigers Vermutung, Kantengraphen, Minor, Kantenkontraktion und relevante Sätze und Lemmata wie Mengers Satz und Vizings Adjazenz-Lemma.