The title says it all. Let $G$ be a (simple undirected finite) graph, and let $G^c$ be the complement of $G$ (i.e. contains edges not in $G$ and no more). Let $M$ be a perfect matching in $G^c$.
How large can the difference between the chromatic number of $G$ and the chromatic number of $G+M$ be?
That is, can we say anything about $\max_M \chi(G+M)-\chi(G)$? (at least some bounds).
I would like to keep the problem in the general setting. If it matters, I am more interested in the special case when $G$ is a regular graph.
Thank you.