# Disjoint Maximum Independent Sets in $\alpha$-critical graphs

Let $G$ be an undirected, simple graph, and let $\alpha(G)$ denote the independence number of $G$, i.e., the size of a maximum independent set (stable set) in $G$. A graph is $\alpha$-critical if for every edge $e$ of $G$, we have $\alpha(G - e) > \alpha(G)$.

Conjecture: for every $\alpha$-critical graph $G$ without isolated vertices, for every maximum independent set $S$ in $G$, there is a maximum independent set $S'$ in $G$ that is disjoint from $S$.

The conjecture is true for the simplest classes of $\alpha$-critical graphs, the graphs $K_n$ ($n \geq 2$) and the odd cycles. It also seems to be true for the list of minor-minimal obstructions to having a vertex cover of size at most five, which are also $\alpha$-critical. Is it true in general?

• Bart, I have Matching Theory''. To send it to you? Commented Feb 12, 2013 at 11:20
• Thanks, Boris. The theorems in the book do not seem to answer my question, unfortunately. Commented Feb 13, 2013 at 9:26
• I arrived at this page looking for Hajnal's theorem. It says: Thm [Hajnal] If G is α-critical, then Δ(G)<= |V(G)|-2α+1. This implies in particular that in a connected α-critical graph α<=(|V(G)|-1)/2, but this cannot be the case for bipartite graphs. So Benjamin's idea will not work so easily. I am also curios if the week conjecture by "took" holds! Observing that a vertex of degree d must be in d different independent sets of order α I am even tempted to ask: Problem Can one find |V(G)|/α disjoint independent sets in any α-critical? Note that |V(G)|/α>=2 for connected α-critical graphs by Commented Jan 21, 2016 at 21:21

Late answer, but for future reference (so that anyone reading this thread won't spend as much time as I did trying to prove the conjecture) the conjecture is false, with the following simple graph as a counterexample. Let $G$ be the following graph

One can see that $\alpha(G) = 4$. It is also easy to see that if we remove any of its edges we obtain a graph with independence number 5, whence it is $\alpha$-critical. The vertex set $S = \{1,4,7,9\}$ (or, alternatively, $S=\{2,5,8,9\}$) is a maximum independent set with the property that $H = G \setminus S$ (the graph formed by removing the vertices in $S$, and all edges incident to them, from $G$) is just the graph consisting of three $K_2$-components. Thus $\alpha(H) = 3$ and therefore the maximum size of any independent set in $G$ disjoint from $S$ is three.

Another reason for reopening this thread is that I would be interested to know if the following weakening of the conjecture could be true:

Weak conj. for every $\alpha$-critical graph $G$ without isolated vertices, there exists a maximum independent set $S$ in $G$ and a maximum independent set $S′$ in $G$ that is disjoint from $S$.

I somehow get the feeling that this is unlikely to be true, however I am unable to find a counterexample. The graph above, that provides a counterexample to the stronger conjecture, does indeed satisfy this weaker version, for example by taking the maximum independent sets $S = \{1,2,4,9\}$ and $S' = \{5,6,7,8\}$. There is one more (connected) graph with a counterexample to the stronger conjecture that I know of;

with $S = \{1,4,7,9\}$.

However, also this graph satisfies the weaker version of the conjecture (take e.g. $S = \{1,3,4,9\}$ and $S' = \{0,6,7,8\}$).

I know of no more counterexamples to the stronger conjecture and I believe that the only graphs that provide counterexamples with less than $11$ vertices are the two graphs mentioned above. Thus I believe that any counterexample to the weaker conjecture would have to have at least $11$ vertices.

Well, take a graph on $n\ge 3$ vertices with exactly one edge. Clearly, it's $(n-1)$-critical, but does not satisfy your conjecture.

• You're right, of course. I should have added the condition that $G$ contains no isolated vertices, which I just did. (I'm used to thinking about the graphs as minor-minimal obstructions to having a vertex cover of a certain size; $\alpha$-critical graphs are only obstructions if they do not have any isolated vertices.) Commented Feb 13, 2013 at 9:28

I don't think so. You really mean maxiMUM, not maxiMAL, right?

If so, take a complete bipartite graph $K_{m,n}$ with $m$ less than $n$, so the maximum critical set is the big part in the bipartition and is of size n. This graph isn't $\alpha$-critical, clearly, but its maximum independent set is so big that there's a pigeonhole problem with finding a disjoint second one.

It seems to me that if you delete edges from G you can only increase the independence number, so (*) do this iteratively without disconnecting G until the result is $\alpha$-critical.

This should give you a counterexample unless this last step (*) is flawed somehow, which might well be the case, I confess - I haven't thought it through. But rather than agonizing about whether it's possible, you can implement this randomly with a computer program, for explicit small m,n, until you have either generated an explicit counterexample, or waited for such a long time as to convince yourself that it's worth trying to find the error. I might do it if I have a chance today.

EDIT -- I was wrong - step (*) is in fact flawed, because it disconnects the graph before it becomes $\alpha$-critical. Interesting!

• I'm pretty sure (*) fails emphatically. As evidence, consider the case in which the edges form a perfect matching. Here $n$ is the maximum stable set still, but since $n>m$ the graph is disconnected. Moreover it fails for $(m,n)=(1,2)$, and I think you should be able to prove that it fails in general using strong induction and observing the new maximum stable set when you remove an edge. Commented Mar 13, 2013 at 17:44
• I do indeed mean maxiMUM rather than maxiMAL. It is known that the alpha-critical bipartite graphs are exactly the perfect matchings, so these cannot give a counterexample: all perfect matchings have two disjoint maximum independent sets. Commented Mar 14, 2013 at 9:09