DEPARTMENT OF MATHEMATICS
       ALGEBRA AND COMBINATORICS SEMINAR

  12 noon THURSDAY 2 DECEMBER 2004  in 67-641

       
           Colouring 4-Cycle Systems

               David A. Pike
      Memorial University of Newfoundland


Abstract
 
An  m-cycle system of order  n  is a partition of the edges
of the complete graph  K_n  into cycles of length  m.
A cycle system is   k-colourable
if its vertex set can be partitioned into  k  sets
(i.e. colour classes) so that no cycle is monochromatic.
A cycle system is   k-chromatic
if it is  k-colourable but is not  (k-1)-colourable;
the system's  chromatic number is this  k.

Whereas colourings of 3-cycle systems (i.e. Steiner triple systems) 
have been well studied, not much is known for colourings of  m-cycle 
systems where  m >= 4.  We focus on  m=4  in particular and prove 
that for each integer  k >= 2, there exists a 4-cycle system with 
chromatic number  k.
For  k=3, we construct a 3-chromatic 4-cycle system of order 49.

This is joint work with Andrea Burgess.



All welcome.