# Preserving the chromatic number of a highly structured graph under two simple operations

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

-
Your operation 'Merge' is usually called edge-contraction. Your operation 'Separate' is usually called joining (!) the vertices $u,v$. I don't understand your game otherwise. Does the player have a goal? – Oliver Sep 7 '11 at 1:27
Guess as to what you are asking: What is an efficient algorithm to identify pairs of nonadjacent vertices $u,v$ such that adding the edge $uv$ increases the chromatic number? If your graphs are general, you will not find such an algorithm, since as you point out, calculating chromatic numbers is NP-hard. However if your graphs all belong to some special class, then perhaps there will be a polynomial algorithm. Or if your graphs are all small, you shouldn't care about the asymptotics anyway. – Oliver Sep 7 '11 at 1:34