The four-in-a-tree problem in triangle-free graphs

DOI10.1007/s00373-009-0867-3zbMath1186.05101arXiv1309.0978OpenAlexW3099919903MaRDI QIDQ844235

Nicolas Derhy, Nicolas Trotignon, Christophe Picouleau

Publication date: 18 January 2010

Published in: Graphs and Combinatorics (Search for Journal in Brave)

Full work available at URL: https://arxiv.org/abs/1309.0978

zbMATH Keywords

triangle-free graphinduced treethree-in-a-tree algorithm

Mathematics Subject Classification ID

Programming involving graphs or networks (90C35) Trees (05C05) Graph theory (including graph drawing) in computer science (68R10) Structural characterization of families of graphs (05C75) Graph algorithms (graph-theoretic aspects) (05C85)

Related Items (7)

The \(k\)-in-a-tree problem for graphs of girth at least \(k\) ⋮ MIP formulations for induced graph optimization problems: a tutorial ⋮ The \(k\)-in-a-path problem for claw-free graphs ⋮ FPT and kernelization algorithms for the induced tree problem ⋮ The (theta, wheel)-free graphs. IV: Induced paths and cycles ⋮ Induced Disjoint Paths in Claw-Free Graphs ⋮ Induced disjoint paths in AT-free graphs

Cites Work

• The three-in-a-tree problem
• On the complexity of testing for odd holes and induced odd paths
• Detecting induced subgraphs
• Unnamed Item
• Unnamed Item

This page was built for publication: The four-in-a-tree problem in triangle-free graphs