Maximal classes for which largest independent set can be found in polynomial time? 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$.
An interesting paper to look at might be:

A. Brandstadt, V. V. Lozin, R. Mosca: Independent Sets of Maximum Weight in Apple-Free Graphs, SIAM Journal on Discrete Mathematics 24 (1) (2010) 239–254. doi:10.1137/090750822

The infinite class of apples is defined as cycles C_k, k>=5, each with a stalk.

You don't mention whether your notion of IS-easiness includes the weighted IS problem. Chair-free graphs (aka fork-free graphs) are known to be IS-easy:

V. E. Alekseev, Polynomial algorithm for finding the largest independent sets in graphs without forks, Discrete Applied Mathematics 135 (1-3) (2004) 3–16. doi:10.1016/S0166-218X(02)00290-1 

The tractability of the weighted case is a non-trivial extension, see:

V. V. Lozin, M. Milanic: A polynomial algorithm to find an independent set of maximum weight in a fork-free graph, Journal of Discrete Algorithms 6 (4) (2008) 595–604. doi:10.1016/j.jda.2008.04.001

Are there any other (interesting) classes where the weighted IS problem is significantly more difficult/intractable/open than the unweighted case?