Improved SDP Coloring of 3-Colorable Graphs from Recursive Gaussian CertificatesResearch Paper
A proper coloring assigns a label to each vertex of a graph so that adjacent vertices have different labels. A graph is three-colorable when such an assignment exists using three labels. Knowing that three colors suffice does not supply the assignment. The approximation question asks how many colors an efficient algorithm can guarantee under that promise.…