# DIMACS Discrete Mathematics Seminar

## Title:

An Elementary Proof of the Cycles-plus-triangle Theorem

## Speaker:

- Horst Sachs
- Ilmenau University and RUTCOR

## Place:

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

## Time:

- 4:30 PM
- Tuesday, December 5, 1995

Abstract:
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