# 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? – Boris Novikov Feb 12 '13 at 11:20
• Thanks, Boris. The theorems in the book do not seem to answer my question, unfortunately. – Bart Jansen Feb 13 '13 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 – Reza Naserasr Jan 21 '16 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.) – Bart Jansen Feb 13 '13 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. – Andrew D. King Mar 13 '13 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. – Bart Jansen Mar 14 '13 at 9:09