Bi-induced sub graphs and stability number

Abstract

We define a 2-parametric hierarchy CLAP (m, n) of bi-hereditary classes of graphs, and show that a maximum stable set can be found in polynomial time within each class CLAP (m, n). The classes can be recognized in polynomial time.

Keywords

• stability number
• hereditary class
• bi-hereditary class
• forbidden induced sub graphs
• forbidden bi-induced sub graphs