Approximation algorithms for Maximum Independent Set on special classes of graphs We know that Maximum Independent Set (MIS) is hard to approximate within a factor of $n^{1-\epsilon}$ for any $\epsilon &gt; 0$ unless P = NP. What are some special classes of graphs for which better approximation algorithms are known?

What are the graphs for which polynomial-time algorithms are known? I know for perfect graphs this is known, but are there other interesting classes of graphs?
There is a truly awesome list of all known graph classes that have some nontrivial algorithms for MIS: see this entry in the graph classes website.