DIMACS Discrete Mathematics Seminar


An Elementary Proof of the Cycles-plus-triangle Theorem


Horst Sachs
Ilmenau University and RUTCOR


Seminar Room 431, CoRE Building,
Busch Campus, Rutgers University.


4:30 PM
Tuesday, December 5, 1995

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.

Document last modified on December 1, 1995