Paw-free graphs (Q1108293)

The graph with vertices \(a, b, c, d\) and edges \(ab, bc, bd, cd\) will be referred to as the paw. A graph \(G\) is called paw-free if it contains no induced subgraph isomorphic to the paw. We characterize paw-free graphs and give polynomial-time algorithms for recognizing them as well as algorithms for finding the largest clique and the largest stable set in a paw-free graph.