Let $G$ be a graph on an even number of vertices, say $2M$. Assume that the largest independent set in $G$ has at most $M$ elements. Is it true that there exists a set of $2m$ vertices (for some $m\leq M$), say $v_1,v_2,\ldots, v_{2m}$, with the following three properties:

1) The induced subgraph on $v_1,\ldots,v_{m-1}$ is an independent set;

2) The induced subgraph on $v_m,\ldots,v_{2m}$ is a clique;

3) Removing these $2m$ vertices from $G$ leaves a graph with no independent set larger than M-m.

It turned out that the claim is not true and Colin provided a counterexample - a cycle on five vertices and an isolated vertex.

A less precise question. Under the same condition - a graph $G$ on $2M$ vertices with no independent set larger than $M$ - could we say something about the structure of $G$ like:

a) $G$ is has a very particular form (say an independent set on $M-1$ vertices and a clique on $M+1$ vertices);

b) Otherwise we can partition the vertex set of into part with even number of vertices (say $2m_i$) so that the induced subgraphs on these sets of vertices have each no independent set larger than $m_i$?

Comment: If we could have such a statement, maybe we could say something more about these small graphs? That is, maybe they could have a very simple structure like a cycle on an odd number of vertices and an isolated edge?

  • 3
    $\begingroup$ You say $M=3$ works - what about a cycle of length $5$ + one isolated vertex? $\endgroup$ – Colin McQuillan Mar 12 '13 at 11:00
  • $\begingroup$ Colin, then take $m=1$ and remove two vertices, one of which is the isolated vertex. $\endgroup$ – Andrew D. King Mar 12 '13 at 18:44
  • $\begingroup$ (I am assuming TOM means $v_1,\ldots, v_m$ are a stable set and $v_{m+1},\ldots,v_{2m}$ are a clique. Is that the case?) $\endgroup$ – Andrew D. King Mar 12 '13 at 19:00
  • 1
    $\begingroup$ In that case, doesn't Colin provide a valid counterexample? $\endgroup$ – Andrew D. King Mar 13 '13 at 5:26
  • 1
    $\begingroup$ Dear TOM. It seems to me that the current statement is not weaker than the original one. That is, if the current statement is true, then by induction on $M$, the original statement is true. Note that condition (3) is equivalent to saying that the after removing these $2m$ vertices we get a graph with independence number exactly $M-m$, since the $2m+1$ from the clique contains at most one vertex from any independent set. $\endgroup$ – Tony Huynh Mar 13 '13 at 5:34

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Browse other questions tagged or ask your own question.