Are there any ways to determine whether the chromatic number of a graph $G$ remains unchanged after a merging operation?

Question

Suppose the current chromatic number is known and vertices $v$ and $u$ are not adjacent. Then we merge these vertices into one. Edges that are originally incident to $u$ or $v$ are now incident to the new vertex. Are there any methods or properties to help identify whether the chromatic number remains the same after this merging operation?

Answer 1

It's no easier than finding the chromatic number to begin with.

If $G$ is any graph with $n$ vertices and $m$ edges, you can start with a matching of size $m$ and keep identifying non-adjacent vertices many times (more precisely, $2m-n$ times) to get $G$.

Assuming you could efficiently determine how vertex identification changes the chromatic number, you could also find the chromatic number of $G$ efficiently, which is hard.

---

Even if we want to know whether the chromatic number changes and not by how much, this is still hard: at least as hard as testing for 3-colorability, which is NP-complete.

Suppose we had an efficient method to determine if vertex identification increases the chromatic number. (It can't decrease the chromatic number, since a $k$-coloring of the new graph induces a $k$-coloring of the old one.) If we want to know if an $m$-edge graph $G$ is $3$-colorable, we can:

• First test if $G$ is bipartite (which is easy). If not, find an odd cycle in $G$; let it have length $2k+1$.
• Let $H$ be a graph consisting only of a $2k+1$-cycle and $m-(2k+1)$ more isolated edges; then $\chi(H)=3$. Starting with $H$, build $G$ by vertex identification.
• If the chromatic number stays the same at every step, then $\chi(G)=3$; if not, then $\chi(G)>3$.