ICM 1998, Berlin, Aug. 18–27

Abstracts of Short Communications and Posters

Section:

13. Combinatorics

1991 Mathematical Subject Classification: 5, 60, 90. Broughan, Kevin, University of Waikato, Hamilton, New Zealand: Computing the minimal colouring of large graphs. Computing the minimal colouring of a simple connected graph of large size is an intractible problem. As well as being NP complete, no known polynomial approximation algorithms are known. Yet minimal colouring is important in scheduling and timetabling applications. The well known sequential algorithm is suitable for graphs with several thousand vertices. The natural structure underlying this method, will be derived. The algorithm will be proved to always return a minimum colouring for some choice of vertex ordering. In addition, the results of computational experience, including comparisons with other approaches and with asymptotic estimates will be given. This represents joint work with Nan Zhu. Reference: G. R. Grimmett and C. J. H. McDiarmid, On colouring random graphs, Math. Proc. Camb. Phil. Soc.77 (1975), 313–324.