The three-in-a-tree problem

DOI10.1007/S00493-010-2334-4MaRDI QIDQ653792zbMATHOpenAlexFDO

Authors Maria Chudnovsky, Paul Seymour

Publication date 19 December 2011

Published in Combinatorica (Search for Journal in Brave)

Full work available at URL https://doi.org/10.1007/s00493-010-2334-4

zbMATH Keywords

induced subgraph testing, theta, pyramid

Mathematics Subject Classification ID

Graph algorithms (graph-theoretic aspects) (05C85) Structural characterization of families of graphs (05C75)

Recommendations

• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• Three-in-a-tree in near linear time
• The four-in-a-tree problem in triangle-free graphs
• FPT and kernelization algorithms for the induced tree problem
• Characterization of partial 3-trees in terms of three structures
• Publication:3334090
• On the SPANNING \(k\)-TREE problem
• Finding induced trees
• Testing for a theta
• Complexity of Finding Embeddings in a k-Tree

Cites work

• Algorithms for Perfectly Contractile Graphs
• Detecting a Theta or a Prism
• On the complexity of testing for odd holes and induced odd paths
• Recognizing Berge graphs

Cited in

(37)

• On the forbidden induced subgraph sandwich problem
• The (theta, wheel)-free graphs. I: Only-prism and only-pyramid graphs
• Detecting a long even hole
• Finding induced trees
• A structure theorem for graphs with no cycle with a unique chord and its consequences
• Three tree-paths
• Finding induced paths of given parity in claw-free graphs
• Clique or hole in claw-free graphs
• Integer programming formulations for the \(k\)-in-a-tree problem in graphs
• The four-in-a-tree problem in triangle-free graphs
• The \(k\)-in-a-tree problem for chordal graphs
• Quasi-Polynomial Time Approximation Schemes for the Maximum Weight Independent Set Problem in \(\boldsymbol{H}\)-Free Graphs
• The structure of (theta, pyramid, 1-wheel, 3-wheel)-free graphs
• FPT and kernelization algorithms for the induced tree problem
• Blazing a trail via matrix multiplications: a faster algorithm for non-shortest induced paths
• Induced disjoint paths in claw-free graphs
• scientific article; zbMATH DE number 4031768 (Why is no real title available?)
• Finding a shortest even hole in polynomial time
• The \(k\)-in-a-path problem for claw-free graphs
• MIP formulations for induced graph optimization problems: a tutorial
• Every tree is 3-equitable
• The \(k\)-in-a-tree problem for graphs of girth at least \(k\)
• Detecting an induced subdivision of \(K_{4}\)
• Testing for a theta
• Faster 3-coloring of small-diameter graphs
• A faster algorithm to recognize even-hole-free graphs
• A class of three-colorable triangle-free graphs
• Detecting a Theta or a Prism
• A faster algorithm to recognize even-hole-free graphs
• The (theta, wheel)-free graphs. IV: Induced paths and cycles
• Detecting an induced net subdivision
• The sandwich problem for decompositions and almost monotone properties
• CIO and ring graphs: deficiency and testing
• Finding a subdivision of a digraph
• Exact Solution Algorithms for the Chordless Cycle Problem
• Maximum weighted induced forests and trees: new formulations and a computational comparative review
• Large Induced Subgraphs via Triangulations and CMSO

This page was built for publication: The three-in-a-tree problem

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