How many more colours do you need if you add to $G$ a maximum matching from $G^c$? 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.
One always has $\chi(G+M)\leq 2\chi(G)$, and this bound does not seem improvable in general. To see the bound itself, note that the only edges of the matching $M$ that can possibly ruin an optimal coloring of $G$ are those between two vertices of the same color class; in particular, we can color $G+M$ by simply creating two new colors for every original color and placing the two nodes on any such violating edge with distinct colors.
To see that this is tight, for any $k$, consider a $k$-partite complete graph with an even number of nodes in each part. It is easy to see that the original graph is $k$-colorable and that adding any perfect matching (which only can have edges within each part) will increase the clique number to $2k$, and so the chromatic number is at least $2k$.