Conference abstracts

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Leonard Soicher

Title: Exploiting symmetry in the computation of the chromatic number of a graph

Abstract: I will describe new algorithms for the proper vertex-colouring of a
graph and the determination of its chromatic number, and the implementation
of these algorithms in GAP, making extensive use of its GRAPE package. In particular,
the GRAPE philosophy is applied to exploit symmetries of the graph under consideration.
These programs have proved effective in determining the chromatic numbers of
many vertex-transitive graphs having up to about 200 vertices, and I will briefly discuss
the application of the programs to the determination of the synchronizing permutation
groups (a problem close to the heart of Peter Cameron).