Let G(n) denote the set of all graphs G that have a Hamiltonian circuit H such that if the edges of H are omitted then the rest of G decomposes into disjoint copies of the complete graph on n vertices (n = 1,2,3,...).
Consider the following statements.
S(n): Every graph from G(n) is n-chromatic.
Obviously, S(1) and S(2) are false.
There are beautiful elementary and simple proofs of the following propositions.
(i) S(4) is true. (ii) If S(n) is true then so is S(n+1) .
Thus S(n) is true for all values of n greater than 3. The case n = 3 , however, is hard. S(3) - now called the cycle-plus-triangles theorem - was formulated and conjectured to be true by Paul Erdos in 1987; his conjecture strengthens a weaker conjecture concerning the stability number of G made by D.Z. Du and D.F. Hsu in 1986. The first proof was given by Herbert Fleischner (Vienna) and Michael Stiebitz (Ilmenau) in 1991; their proof, which is based on a general list- colouring principle of N. Alon and M. Tarsi published 1992, is non-elementary (non-constructive).
In this talk, an elementary proof is given for the stronger proposition that the number of the 3-partitionings induced by the 3-colourings (i.e., the number of non-equivalent 3-colourings) is odd.