The three-in-a-tree problem

DOI10.1007/S00493-010-2334-4MaRDI QIDQ653792zbMATH OpenOpenAlexFDO

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

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

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
• scientific article; zbMATH DE number 3866594
• 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

(44)

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

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)