Algorithmic bounds for the chromatic number†
Ingo Schiermeyer · Optimization · 2008
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.