The k-in-a-path problem for claw-free graphs

Abstract

Testing whether there is an induced path in a graph spanning k given vertices is already NP-complete in general graphs when k=3. We show how to solve this problem in polynomial time on claw-free graphs, when k is not part of the input but an arbitrarily fixed integer.

12 pages, 1 figure, STACS 2010

References in corpus (3)

• Detecting induced subgraphs
• The $k$-in-a-tree problem for graphs of girth at least~$k$
• The four-in-a-tree problem in triangle-free graphs

Cited by in corpus (6)

• Vertex elimination orderings for hereditary graph classes
• Three-in-a-Tree in Near Linear Time
• The (theta, wheel)-free graphs Part IV: induced paths and cycles
• (Theta, triangle)-free and (even hole, $K_4$)-free graphs. Part 1 : Layered wheels
• Induced Disjoint Paths in Claw-Free Graphs
• Induced Disjoint Paths in Circular-Arc Graphs in Linear Time