1
$\begingroup$

An independent set is a set of vertices in a graph, no two of which are adjacent. A maximum independent set is an independent set of the largest possible size for a given graph. The size of a maximum independent set is called the independence number of $G$ and is usually denoted by $α(G)$.

It is easy to see that $α(G)=1$ if and only if $G$ is a complete graph. So if $α(G)=2$, is there also a characterization? And go on, for $α(G)=3$...

If there is no characterization, are there any necessary or sufficient conditions? For example, it appears that these graphs are not too sparse. Is there a lower bound on the number of their edges?

Improve this question
$\endgroup$
4
  • 5
    $\begingroup$ The complement of a graph with $\alpha(G)\leq 2$ is a triangle-free graph. There is no simple characterization. See en.wikipedia.org/wiki/Triangle-free_graph for some information. $\endgroup$
    – Richard Stanley
    Commented Oct 15, 2023 at 13:42
  • 1
    $\begingroup$ A graph has independence number $\le 2$ if and only if its complement is triangle-free. Of course this is just a restatement of the definition, but this may still be a helpful keyword, and it may also indicate that a more nontrivial characterization doesn't exist. $\endgroup$
    – Tobias Fritz
    Commented Oct 15, 2023 at 13:42
  • $\begingroup$ One solution is (2,0)-colorable graphs. Their vertices can be partitioned in 2 cliques and they are complements of bipartite graphs. $\endgroup$
    – joro
    Commented Oct 15, 2023 at 15:25
  • 1
    $\begingroup$ @joro I don't understand what you mean. $\endgroup$
    – domotorp
    Commented Oct 15, 2023 at 18:42

0

Reset to default

You must log in to answer this question.

Browse other questions tagged .