Ringel-Kotzig-Vermutung

aus Wikipedia, der freien Enzyklopädie
Zur Navigation springen Zur Suche springen

Die Ringel-Kotzig-Vermutung ist eine Annahme über die Zerlegbarkeit von Graphen. Demnach lassen sich alle vollständigen Graphen mit Knoten zyklisch in Kopien eines beliebigen Baums mit Kanten zerlegen. Die Ringel-Kotzig-Vermutung erweitert die ringelsche Vermutung, indem sie von beliebigen zu zyklischen Zerlegungen übergeht.

Anstatt die Ringel-Kotzig-Vermutung direkt zu beweisen, konzentriert sich die Forschung auf den Beweis der Graziöser-Baum-Vermutung. Aus dieser lässt sich die Ringel-Kotzig-Vermutung direkt ableiten.

Die Vermutung ist nach Gerhard Ringel und Anton Kotzig benannt.

Ringelsche Vermutung

[Bearbeiten | Quelltext bearbeiten]

Gerhard Ringel stellte diese Vermutung im Juni 1963 auf einer Tagung in Smolenice vor. Sie wird im Tagungsband als Problem 25 aufgeführt und lautet:

Es wird vermutet, dass das vollständige -Eck in Untergraphen zerlegt werden kann, die alle isomorph zu einem vorgegebenen Baum mit Kanten sind.[1]

Der vollständige Graph mit Knoten wird hier als vollständiges -Eck bezeichnet.

Einzelnachweise

[Bearbeiten | Quelltext bearbeiten]
  1. Miroslav Fiedler: Theory of Graphs and its Applications. Proceedings of the Symposium held in Smolenice in June 1963. Publishing House of the Czechoslovak Academy of Sciences, Prag 1964, S. 162.