Forbidden Subgraph Conditions

In 1980 Minty showed that if a graph is claw-free then there is an efficient algorithm for finding a maximum independent set. When Ed Scheinerman visited VCU in the fall he suggested to Patrick and me a continued pursuit of these forbidden-subgraph conditions. I had no idea at the time that claw-free graphs were just the tip of the iceberg and that there is a well-developed literature on this subject due to V. Alekseev, C. ArbibA. Brandstadt, C. De Simone, J-L Fouquet, M. Gerber, V. Giakoumakis, A. Hertz, V. Lozin, R. Mosca, and A. Sassano, among others.

Here are some of the classes, mostly from the list in Brandstadt and Mosca, 2004:

  1. P4-free
  2. (C4,2K2)-free (Hertz, 1997)
  3. (Banner-P8)-free (Gerber, Hertz, Lozin, 2004)
  4. Chair-free (Alekseev, 2004)
  5. (P5-A)-free (Lozin, Mosca, 2009)
  6. (P5,K3,3-e)-free (Lozin, Mosca, 2009)
  7. (P,S2,2,2)-free (Gerber, Lozin, 2003)
  8. (P5,diamond)-free (Arbib, Mosca, 2000)
  9. (P5,co-chair)-free (Brandstadt, Mosca, 2004)
  10. (P5,co-P)-free (Brandstadt, Mosca, 2004)
  11. (P5,P)-free (Lozin, 2000; Brandstadt, Lozin, 2001)
  12. (P5,bull)-free (De Simone, 1993)
  13. (P5,house)-free (Hoang, 1983)
  14. (P5,gem)-free (Mosca, 1997; Brandstadt, Kratsch, 2001)
  15. (P5,K4-e)-free (Arbib, Mosca, 2002; Brandstadt, 2004)

 

Advertisements

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s