Let G be a graph on n*k vertices comprised of n k-cliques, for n, k positive integers.

Define two operations: 'Merge' nonadjacent vertices u and v into a single vertex w such that w is adjacent to every vertex that at least one of u and v was adjacent to.

'Separate' nonadjacent vertices u and v by including the edge (u, v) in G.

The chromatic number of G is initially k.

Imagine a game being played with the above as follows: A user selects a pair of nonadjacent vertices, and either merges or separates them.

After each move by the user, an algorithm detects every pair of vertices that would increase the chromatic number if merged, and separates them.

It also detects every pair of vertices that would increase the chromatic number if they were separated, and merges them.

I'd like help coming up with an algorithm, or determining that the structure doesn't help do this efficiently.

I know that in general find the chromatic number is an np-hard problem. I was wondering if anyone either had thoughts on this problem, or could point me to a paper that seems related.

Motivation: These graphs arise naturally in solving logic puzzles which have n categories of k elements each. E.g., 5 houses, 5 cars, 5 professions, 5 pets. We draw an edge between the vertices containing elements which are known to be disassociated (the owner of the red house doesn't drive a Ford), and merge vertices containing elements known to be associated.

Thanks, Dave