Given a graph, is there an efficient algorithm to color its vertices such that any two adjacent vertices are different colors, and any two non-adjacent vertices are the same color, and to do so with the minimum number of colors?
What I have realized is that, except for the trivial case where the graph has no edges, it must be connected, otherwise such a coloring is impossible: take any existing edge u-v, and it's clear that any other vertex x must be joined to one of its endpoints, otherwise color(x) = u and color(x) = v, contradicting color(u) != color(v).
Any other ideas for how to solve this problem?
Let's consider the graph with the complement of the edge set, i.e. vertices are adjacent when they are not in the original graph and vice-versa.
In this new graph vertices that are adjacent must have the same color. This means, all vertices forming a connected component must have the same color. Further, if a coloring is possible, this connected component must be a complete graph (i.e. all vertices are pairwise adjacent) because otherwise there are two nodes in the component that are connected in the original gaph and must therefore have different color: a contradiction.
Now, each connected component in the new graph must have a different color.