Ringel-Kotzig-Vermutung

Die Ringel-Kotzig-Vermutung ist eine Annahme über die Zerlegbarkeit von Graphen. Demnach lassen sich alle vollständigen Graphen mit ${\displaystyle 2n+1}$ Knoten zyklisch in ${\displaystyle 2n+1}$ Kopien eines beliebigen Baums mit ${\displaystyle n}$ 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

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 ${\displaystyle (2n+1)}$-Eck in ${\displaystyle 2n+1}$ Untergraphen zerlegt werden kann, die alle isomorph zu einem vorgegebenen Baum mit ${\displaystyle n}$ Kanten sind.[1]

Der vollständige Graph mit ${\displaystyle 2n+1}$ Knoten wird hier als vollständiges ${\displaystyle (2n+1)}$-Eck bezeichnet.

Einzelnachweise

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.