Ringel-Kotzig-assumption

The Ringel-Kotzig conjecture is an assumption about the decomposability of graphs . Accordingly, all complete graphs with nodes can be decomposed cyclically into copies of any tree with edges . The Ringel-Kotzig conjecture extends the Ringel conjecture by moving from arbitrary to cyclic decompositions. ${\displaystyle 2n+1}$ ${\displaystyle 2n+1}$ ${\displaystyle n}$

Rather than proving the Ringel-Kotzig Conjecture directly, the research focuses on proving the Graceful Tree Conjecture . The Ringel-Kotzig conjecture can be derived directly from this.

The conjecture is named after Gerhard Ringel and Anton Kotzig .

Ringel's conjecture

Gerhard Ringel presented this assumption in June 1963 at a conference in Smolenice . It is listed in the conference proceedings as problem 25 and reads:

It is conjectured that the complete corner can be broken down into subgraphs, which are all isomorphic to a given tree with edges. ${\displaystyle (2n+1)}$ ${\displaystyle 2n+1}$ ${\displaystyle n}$

The complete graph with nodes is referred to here as a complete corner. ${\displaystyle 2n+1}$ ${\displaystyle (2n+1)}$

Individual evidence

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, Prague 1964, p. 162