On approximate graph colouring and MAX-k-CUT algorithms based on the υ-function

The problem of colouring a k-colourable graph is well-known to be NP-complete, for k greater than or equal to 3. The MAX-k-CUT approach to approximate k-colouring is to assign k colours to all of the vertices in polynomial time such that the fraction of 'defect edges' ( with endpoints of the same colour) is provably small. The best known approximation was obtained by Frieze and Jerrum ( 1997), using a semidefinite programming ( SDP) relaxation which is related to the Lovasz theta-function. In a related work, Karger et al. ( 1998) devised approximation algorithms for colouring k-colourable graphs exactly in polynomial time with as few colours as possible. They also used an SDP relaxation related to the theta-function. In this paper we further explore semidefinite programming relaxations where graph colouring is viewed as a satisfiability problem, as considered in De Klerk et al. ( 2000). We first show that the approximation to the chromatic number suggested in De Klerk et al. ( 2000) is bounded from above by the Lovasz theta-function. The underlying semidefinite programming relaxation in De Klerk et al. ( 2000) involves a lifting of the approximation space, which in turn suggests a provably good MAX-k-CUT algorithm. We show that of our algorithm is closely related to that of Frieze and Jerrum; thus we can sharpen their approximation guarantees for MAX-k-CUT for small fixed values of k. For example, if k = 3 we can improve their bound from 0.832718 to 0.836008, and for k = 4 from 0.850301 to 0.857487. We also give a new asymptotic analysis of the Frieze-Jerrum rounding scheme, that provides a unifying proof of the main results of both Frieze and Jerrum ( 1997) and Karger et al. ( 1998) for k much greater than 0.