Maximum Clique, Maximum Independent Set, and Graph Coloring Problems
Jeffrey Pattillo, Sergiy I. Butenko · Wiley Encyclopedia of Operations Research and Management Science · 2011
Abstract This article introduces the closely related maximum clique, maximum independent set, graph coloring, and minimum clique partitioning problems. The survey includes some of the most important results concerning these problems, including their computational complexity, known bounds, mathematical programming formulations, and exact and heuristic algorithms to solve them.