Algorithmic bounds for the chromatic number†

†Dedicated to H. Th. Jongen on the occasion of his 60th birthday.

Abstract

A k-colouring of a graph G is an assignment of k different colours to the vertices of G such that adjacent vertices receive different colours. The minimum cardinality k for which G has a k-colouring is called the chromatic number of G and is denoted by χ(G). Its computation is NP-hard. It is not difficult to colour the vertices of a graph in linear time using at most Δ(G) + 1 colours, where Δ(G) is the maximum vertex degree of a given graph G. Moreover, the classical theorem of Brooks states that χ(G) ≤ Δ(G) unless G is a complete graph or an odd cycle. We will strengthen the upper bound of Δ + 1 by considering additional parameters in terms of vertex degrees and the clique number. These new bounds will be accompanied by polynomial time algorithms attaining these improved bounds.

†Dedicated to H. Th. Jongen on the occasion of his 60th birthday.

Keywords:

• graph colouring
• algorithm

2000 Mathematical Subject Classifications: :

• 05C15
• 05C85

Acknowledgements

Parts of this research were performed within the RIP program (Research in Pairs) at the Mathematisches Forschungsinstitut Oberwolfach. Hospitality and financial support are gratefully acknowledged.

Notes

†Dedicated to H. Th. Jongen on the occasion of his 60th birthday.