The ISGCI lists over 1100 classes of graphs. For many of these we know whether INDEPENDENT SET can be decided in polynomial time; these are sometimes called IS-easy classes. I would like to compile a list of maximal IS-easy classes. These classes together form the boundary of (known) tractability for this problem.
Since one can just add a finite number of graphs to any infinite IS-easy class without affecting tractability, some restrictions are in order. Let's restrict the classes to those that are hereditary (closed under taking of induced subgraphs, or equivalently, defined by a set of excluded induced subgraphs). Moreover, let's consider only those families that are X-free for a set X with a small description. There might are also be infinite ascending chains of tractable classes (such as $(P,\text{star}_{1,2,k})$-free and the classes described by David Eppstein below), but let's restrict attention to classes that have actually been proved to be IS-easy.
Here are the ones I know of:
- perfect graphs
- $(P,\text{star}_{1,2,5})$-free
- $(K_{3,3}-e, P_5)$-free
- co-Meyniel
- nearly bipartite
- chair-free
- ($P_5$,cricket)-free
- $(P_5,K_{n,n})$-free (for any fixed $n$)
- $(P_5, X_{82}, X_{83})$-free
Are other such maximal classes known?
Edit: See also a related question asked by Yaroslav Bulatov dealing with classes defined by excluded minors what is easy for minor-excluded graphs? and see Global properties of hereditary classes? for a more general question I asked previously about hereditary classes.
As Jukka Suomela points out in comments, the minor-excluded case is also interesting (and would make an interesting question), but this is not the focus here.
To avoid David's example, a maximal class should also be definable as the X-free graphs, where not every graph in X has an independent vertex.
Classes given in answers below:
- apple-free (suggested by Standa Živný)
- ($P_5$,house)-free (suggested by David Eppstein)
- ($K_2 \cup$ claw)-free (suggested by David Eppstein)
Added 2013-10-09: the recent result by Lokshtanov, Vatshelle and Villanger, mentioned by Martin Vatshelle in an answer, supersedes some of the previously known maximal classes.
In particular, $P_5$-free being IS-easy subsumes ($P_5$,cricket)-free, ($P_5$,$K_{n,n}$)-free, ($P_5$,$X_{82}$,$X_{83}$)-free, and ($P_5$,house)-free all being IS-easy.
This means that all the hereditary graph classes defined by a single forbidden induced subgraph with up to five vertices can now be definitively classified as IS-easy or not IS-easy.
Unfortunately the proof that $P_5$-free graphs form an IS-easy class does not seem to work for $P_6$-free graphs, so the next frontier is to classify all the hereditary graph classes defined by a single six-vertex graph.
I remain especially interested in IS-easy classes of the form $X$-free for some collection $X$ of graphs with infinitely many isomorphism classes, yet where $Y$-free is not IS-easy for any $Y \subset X$.