Finding induced paths of given parity in claw-free graphs

DOI10.1007/978-3-642-11409-0_30MaRDI QIDQ5851119zbMATH OpenOpenAlexFDO

Authors Pim Van 't Hof, Marcin Kamiński, Daniël Paulusma

Publication date 21 January 2010

Published in Graph-Theoretic Concepts in Computer Science (Search for Journal in Brave)

Full work available at URL http://dro.dur.ac.uk/9019/1/9019.pdf

zbMATH Keywords

NP-completenessclaw-free graphinduced cycleeven induced patheven length pathodd induced pathodd length pathParity Path problem

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Analysis of algorithms and problem complexity (68Q25) Paths and cycles (05C38)

Recommendations

• Finding induced paths of given parity in claw-free graphs
• Finding an induced path of given parity in planar graphs in polynomial time
• The \(k\)-in-a-path problem for claw-free graphs
• Even pairs in claw-free perfect graphs
• The \(k\)-in-a-path problem for claw-free graphs

Cited in

(4)

• The \(k\)-in-a-path problem for claw-free graphs
• Finding an induced path of given parity in planar graphs in polynomial time
• The \(k\)-in-a-path problem for claw-free graphs
• Finding induced paths of given parity in claw-free graphs

This page was built for publication: Finding induced paths of given parity in claw-free graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5851119)