Finding induced paths in claw-free graphs

Jiri Fiala

Abstract

joint work with M. Kaminski, B. Lidicky, and D. Paulusma

We show that for a fixed number of terminals, it is possible to find in a polynomial time an induced path in a claw-free graph that passes through the given set of terminals. The core part of the proof is based on a structural characterization of quasi-line graphs by Chudnovsky and Seymour.