0
$\begingroup$

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.

Improve this question
$\endgroup$
2
  • 1
    $\begingroup$ 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... $\endgroup$
    – Jason Gaitonde
    Nov 15, 2020 at 6:12
  • $\begingroup$ @J.G Okay. I think your answer is correct. Please post it as an answer. $\endgroup$
    – Cyriac Antony
    Nov 15, 2020 at 6:40

1 Answer 1

Reset to default
2
$\begingroup$

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

Improve this answer
$\endgroup$
2
  • $\begingroup$ Are there any simple structures that ensure that the difference $\chi(G+M)-\chi(G)$ is small? eg: $G$ is $2K_2$-free. $\endgroup$
    – Cyriac Antony
    Nov 17, 2020 at 3:27
  • $\begingroup$ @CyriacAntony no idea, but that's a nice question! $\endgroup$
    – Jason Gaitonde
    Nov 21, 2020 at 16:34

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.