imported>Fan-vom-Wiki: format

2024-02-13T03:14:23Z

format

Neue Seite

Die '''Ringel-Kotzig-Vermutung''' ist eine Annahme über die Zerlegbarkeit von [[Graph (Graphentheorie)|Graphen]]. Demnach lassen sich alle [[Vollständiger Graph|vollständigen Graphen]] mit <math>2n+1</math> Knoten zyklisch in <math>2n+1</math> Kopien eines beliebigen [[Baum (Graphentheorie)|Baums]] mit <math>n</math> [[Kante (Graphentheorie)|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 <math>(2n+1)</math>-Eck in <math>2n+1</math> Untergraphen zerlegt werden kann, die alle isomorph zu einem vorgegebenen Baum mit <math>n</math> Kanten sind.''<ref>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.</ref>
Der vollständige Graph mit <math>2n+1</math> Knoten wird hier als vollständiges <math>(2n+1)</math>-Eck bezeichnet.

== Einzelnachweise ==
<references/>

[[Kategorie:Vermutung (Graphentheorie)]]

Ringel-Kotzig-Vermutung - Versionsgeschichte

imported>Fan-vom-Wiki: format