Graph Coloring and Semidefinite Rank

Renee Mirka, Devin Smedira, David P. Williamson

This paper considers the interplay between semidefinite programming, matrix rank, and graph coloring. Karger, Motwani, and Sudan \cite{KMS98} give a vector program for which a colo…