An s-graph is a graph with two kinds of edges: subdivisible edges and real edges. A realisationof an s-graph B is any graph obtained by subdividing subdivisible edges of B into pathsof arbitrary length (at least one). Given an s-graph B, we study the decision problem 175whose instance is a graph G and question is "Does G contain a realisation of B as an inducedsubgraph?". For several B's, the complexity of 17B is known and here we give the complexityfor several more. Our NP-completeness proofs for Π_B'srely on the NP-completeness proof of thefollowing problem. Let &be a set of graphs anddbe an integer. Let Γ_&~dbe the problemwhose instance is (G, x, y) where G is a graph whose maximum degree is at most d, withno induced subgraph in &andx, y∈V (G)are two non-adjacent vertices of degree 2.The question is "Does G contain an induced cycle passing through x, y?". Among severalresults, we prove that Γ_N~3is NP-complete. We give a simple criterion on connected graph H to decide whether Γ_(H)~(+∞)is polynomial or NP-complete. The cases rely on thealgorithm three-in-a-tree, due to Chudnovsky and Seymour.
展开▼
