Forbidden subgraphs implying the MIN-algorithm gives a maximum independent set

摘要

The well-known greedy algorithm MIN for finding a maximal independent set in a graph G is based on recursively removing the closed neighborhood of a vertex which has (in the currently existing graph) minimum degree. We give a forbidden induced subgraph condition under which algorithm MIN always results in finding a maximum independent set of G, and hence yields the exact value of the independence number of G in polynomial time.