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)$-freeco-Meynielnearly bipartitechair-free($P_5$,cricket)-free$(P_5,K_{n,n})$-free (for any fixed $n$)$(P_5, X_{82}, X_{83})$-freeAre 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)-freeall 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$.
Maximal classes for which largest independent set can be found in polynomial time?
ds.algorithms;graph theory;co.combinatorics;graph classes
The question is already a bit older, but ISGCI can be of some help here.When you start the ISGCI Java application and go to the menu Problems -> Boundary/Open classes -> Independent set, you get a dialog with 3 lists.The list Maximal P contains all classes C (in ISGCI) on which IS can be solved in polynomial time, such that there is a minimal superclass of C on which IS is not known to be in P (i.e. NP-complete, open, or unknown to ISGCI). Selecting a class and clicking 'Draw' will draw the class and the superclasses that are found by walking BFS-style up the inclusion hierarchy as far as is needed to find a class on which IS is not known to be in P.The list Minimal NP-complete goes the other way around: It contains classes on which IS is NP-complete, such that not all maximal subclasses are also NP-complete. Drawing goes down in the hierarchy until a not-NP-complete class is found.The open list contains classes for which the problem is either open or unknown. Drawing walks over super/subclasses until a class is reached that is not open.When creating a drawing it is a good idea to set the colouring to the Independent Set problem (Problems -> Colour for problem -> Independent set).With regard to Standa Zivny's question, the following 20 classes are listed in ISGCI with known complexity for the unweighted IS problem, but with unknown complexity for the weighted case (ISGCI cannot distinguish between simple and complicated polynomial algorithms):gc_11 extended P4-ladengc_128 EPTgc_415 well coveredgc_428 (K3,3-e,P5,X98)-freegc_648 (K3,3-e,P5)-freegc_752 co-hereditary clique-Hellygc_756 (E,P)-freegc_757 (P,T2)-freegc_758 (P,P8)-freegc_759 (K3,3-e,P5,X99)-freegc_808 (C6,K3,3+e,P,P7,X37,X41)-freegc_811 (P,star1,2,5)-freegc_812 (P5,P2  P3)-freegc_813 (P,P7)-freegc_818 (P,star1,2,3)-freegc_819 (P,star1,2,4)-freegc_841 (2K3 + e,A,C6,E,K3,3-e,P6,R,X166,X167,X169,X170,X171,X172,X18,X45,X5,X58,X84,X95,X98,A,C6,E,P6,R,X166,X167,X169,X170,X171,X172,X18,X45,X5,X58,X84,X95,X98,antenna,co-antenna,co-domino,co-fish,co-twin-house,domino,fish,twin-house)-freegc_894 co-circular perfectgc_895 strongly circular perfect (3K2,E,P2  P4,net)-freeNo doubt a number of these will have known algorithms for the weighted case as well. Additions and corrections are always welcome at the address given on the ISGCI web page!