# 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.

• What kind of bounds do you have in mind? In general, I don’t think any bound on the difference can beat the original chromatic number itself, i.e I think for every $k$, you can find a regular graph with chromatic number $k$ such that adding a perfect matching causes it to double (consider complete $k$-partite graphs and add the edges within each part). This should be tight—given the original optimal coloring, make two new colors for each original color to get a valid coloring to fix any edge from the perfect matching connecting two vertices of same original color. But I could be wrong...
– J.G
Nov 15 '20 at 6:12
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$$.
• Are there any simple structures that ensure that the difference $\chi(G+M)-\chi(G)$ is small? eg: $G$ is $2K_2$-free. Nov 17 '20 at 3:27