A matrix k-coloring of G is a n × n symmetric positive semidefinite matrix M such that mii £ 1 and mij = - 1/(k - 1) if (i, j) Î E. Fact: A graph admits a matrix k-coloring if and only if it admits a vector k-coloring. From M a Cholesky decomposition provides the vectors. The matrix chromatic number of G can be found by solving the following semidefinite programming problem: Given the optimal M, a set of vectors ui is computed. Then in order to color the graph k is computed from the optimal a as k := [1 - 1/a].

---