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.

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