<p>One always has <span class="math-container">$\chi(G+M)\leq 2\chi(G)$</span>, and this bound does not seem improvable in general. To see the bound itself, note that the only edges of the matching <span class="math-container">$M$</span> that can possibly ruin an optimal coloring of <span class="math-container">$G$</span> are those between two vertices of the same color class; in particular, we can color <span class="math-container">$G+M$</span> by simply creating two new colors for every original color and placing the two nodes on any such violating edge with distinct colors.</p>
<p>To see that this is tight, for any <span class="math-container">$k$</span>, consider a <span class="math-container">$k$</span>-partite complete graph with an even number of nodes in each part. It is easy to see that the original graph is <span class="math-container">$k$</span>-colorable and that adding any perfect matching (which only can have edges within each part) will increase the clique number to <span class="math-container">$2k$</span>, and so the chromatic number is at least <span class="math-container">$2k$</span>.</p>

CC BY-SA 4.0
2020-11-17T03:27:46.423Z
Are there any simple structures that ensure that the difference $\chi(G+M)-\chi(G)$ is small? eg: $G$ is $2K_2$-free.
Cyriac Antony
CC BY-SA 4.0
2020-11-21T16:34:14.827Z
@CyriacAntony no idea, but that's a nice question!
Jason Gaitonde
CC BY-SA 4.0
2020-11-16T19:13:46.737Z
2020-11-16T19:13:46.737Z
Jason Gaitonde
<p>The title says it all. Let <span class="math-container">$G$</span> be a (simple undirected finite) graph, and let <span class="math-container">$G^c$</span> be the complement of <span class="math-container">$G$</span> (i.e. contains edges not in <span class="math-container">$G$</span> and no more). Let <span class="math-container">$M$</span> be a perfect matching in <span class="math-container">$G^c$</span>.<br />
<strong>How large can the difference between the chromatic number of <span class="math-container">$G$</span> and the chromatic number of <span class="math-container">$G+M$</span> be?</strong><br />
That is, can we say anything about <span class="math-container">$\max_M \chi(G+M)-\chi(G)$</span>? (at least some bounds).</p>
<p>I would like to keep the problem in the general setting. If it matters, I am more interested in the special case when <span class="math-container">$G$</span> is a regular graph.</p>
<p>Thank you.</p>

CC BY-SA 4.0
2020-11-15T06:12:43.580Z
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...
Jason Gaitonde
CC BY-SA 4.0
2020-11-15T06:40:49.103Z
@J.G Okay. I think your answer is correct. Please post it as an answer.
Cyriac Antony
<graph-theory><graph-colouring>
How many more colours do you need if you add to $G$ a maximum matching from $G^c$?
Cyriac Antony
# How many more colours do you need if you add to $G$ a maximum matching from $G^c$?

(Asked by: username_0 on 2020-11-15)

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.

**Tags:** graph-theory, graph-colouring
> **Comments:**
> **username_1**: 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...  
> **username_0**: @J.G Okay. I think your answer is correct. Please post it as an answer.  

---

## 1 answers

### Answer by username_1 on 2020-11-16. Score: 2 | Accepted answer

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

> **Comments:**
> **username_0**: Are there any simple structures that ensure that the difference $\chi(G+M)-\chi(G)$ is small? eg: $G$ is $2K_2$-free.  
> **username_1**: @CyriacAntony no idea, but that's a nice question!  

---

