Ringel-Kotzig-Vermutung

Die Ringel-Kotzig-Vermutung ist eine Annahme über die Zerlegbarkeit von Graphen. Demnach lassen sich alle vollständigen Graphen mit $2n+1$ Knoten zyklisch in $2n+1$ Kopien eines beliebigen Baums mit $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 $(2n+1)$ -Eck in $2n+1$ Untergraphen zerlegt werden kann, die alle isomorph zu einem vorgegebenen Baum mit $n$ Kanten sind.[1]

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

Einzelnachweise

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

This article is issued from Wikipedia. The text is licensed under Creative Commons - Attribution - Sharealike. The authors of the article are listed here. Additional terms may apply for the media files, click on images to show image meta data.

[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