Direkt zum Inhalt

Lexikon der Mathematik: Hajós-Konstruktion

ein Verfahren, um jeden Graphen G, der für k ∈ ℕ eine chromatische Zahl χ(G) ≥ k besitzt, schrittweise aus einem vollständigen Graphen Kk zu gewinnen.

Im folgenden bezeichne Ωk die Klasse aller Graphen G mit χ(G) ≥ k. Einer Idee G. Hajós (1961) folgend, erhält man mittels der beiden unten angeführten Operationen aus Graphen, die in Ωk liegen, neue Graphen, die wieder zu Ωk gehören.

  1. (1.) Durch Identifikation zweier nicht adjazenter Ecken eines Graphen aus Ωk.
  2. (2.) Sind G und G′ zwei disjunkte Graphen aus der Klasse Ωk und uvK(G) sowie u′V′K(G′), so erhält man die sogenannte Hajós-Vereinigung der beiden Graphen G und G′ wie folgt: Man entferne die beiden Kanten uv und u′v′, identifiziere u mit u′ und füge danach die neue Kante vv′ hinzu.

Ein Graph G heißt k-konstruierbar, wenn man ihn, ausgehend von dem vollständigen Graphen Kk, durch wiederholtes Anwenden von (1.) und (2.) erzeugen kann.

Wie man leicht sieht, sind alle k-konstruierbaren Graphen, und damit auch deren Obergraphen, mindestens k-chromatisch. Bemerkenswert ist, daß Hajós 1961 auch die Umkehrung beweisen konnte.

Jeder Graph G aus Ωk enthält einen k-konstruierbaren Teilgraphen.

Schreiben Sie uns!

Wenn Sie inhaltliche Anmerkungen zu diesem Artikel haben, können Sie die Redaktion per E-Mail informieren. Wir lesen Ihre Zuschrift, bitten jedoch um Verständnis, dass wir nicht jede beantworten können.

  • Die Autoren
- Prof. Dr. Guido Walz

Partnerinhalte

Bitte erlauben Sie Javascript, um die volle Funktionalität von Spektrum.de zu erhalten.