On algorithms for (P5,gem)-free graphs

We present O(n2) time recognition algorithms for chordal gem-free graphs and for (P5,gem)-free graphs. Using a characterization of (P5,gem)-free graphs by their prime graphs with respect to modular decomposition and their modular decomposition trees [A. Brandstädt, D. Kratsch, On the structure of (P5,gem)-free graphs, Discrete Appl. Math. 145 (2005), 155-166], we give linear time algorithms for the following NP-complete problems on (P5,gem)-free graphs: Minimum Coloring; Maximum Weight Stable Set; Maximum Weight Clique; and Minimum Clique Cover.