On Algorithms for (P5,Gem)-Free Graphs
Hans L. Bodlaender, Andreas Brandstädt, Dieter Kratsch, Mengjiao Rao, Jeremy Spinrad · 2003
A graph is (P5,gem)-free, when it does not contain P5 (an induced path with five vertices) or a gem (a graph formed by making an universal vertex adjacent to each of the four vertices of the induced path P4) as an induced subgraph. We present O(n 2) time recognition algorithms for chordal gem-free 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 [6], we give linear time algorithms for the following NP-complete problems on (P5,gem)-free graphs: Minimum