THE OPERATOR Ϋ FOR THE CHROMATIC NUMBER OF A GRAPH.

We investigate hierarchies of semidefinite approximations for the chromatic number X(G) of a graph G. We introduce an operator Ϋ mapping any graph parameter ß(G), nested between the stability number α(G) and X(Ḡ), to a new graph parameter Ϋß(G), nested between α(Ḡ) and X(G); Ϋß(G) is polynomial time computable if ß(G) is. As an application, there is no polynomial time computable graph parameter nested between the fractional chromatic number X*(·) and X(·) unless P = NP. Moreover, based on the Motzkin-Straus formulation for α(G), we give (quadratically constrained) quadratic and copositive programming formulations for X(G). Under some mild assumptions, n/ß(G) ≤ Ϋß(G), but, while n/ß(G) remains below X*(G), Ϋß(G) can reach X(G) (e.g., for ß(·) = α(·)). We also define new polynomial time computable lower bounds for X(G), improving the classic Lovász theta number (and its strengthenings obtained by adding nonnegativity and triangle inequalities); experimental results on Hamming graphs, Kneser graphs, and DIMACS benchmark graphs will be given in the follow-up paper [N. Gvozdenović and M. Laurent, SIAM J. Optim., 19 (2008), pp. 592-615]. [ABSTRACT FROM AUTHOR]