Penta is the configuration shown in Figure 1(a), where continuous lines represent edges and dotted lines represent non-edges. The vertex $u$ in Figure 1(a) is called the center of Penta. A graph $G$ is called a pentagraph if every induced subgraph $H$ of $G$ has a vertex $v$ which is not a center of induced Penta in $H$.
The class of pentagraphs is a common generalization of chordal (triangulated) graphs and Mahadev graphs.
We construct a polynomial-time algorithm that either find a maximum stable
set of $G$ or concludes that $G$ is not a pentagraph.
Paper Available at:
ftp://dimacs.rutgers.edu/pub/dimacs/TechnicalReports/TechReports/2001/2001-07.ps.gz
DIMACS Home Page