CODEWITHSUNDEEP
algorithmgraph-coloring
cupcake111680
cupcake111680

Reputation: 3

Can a graph be colored such that adjacent vertices are different colors and non-adjacent vertices are the same color?

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?

Upvotes: 0

Views: 1509

Answers (1)

Henry
Henry

Reputation: 43788

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.

Upvotes: 0

Related Questions