THE THREE-IN-A-TREE PROBLEM

Research output: Contribution to journalArticle

29 Scopus citations

Abstract

We show that there is a polynomial time algorithm that, given three vertices of a graph, tests whether there is an induced subgraph that is a tree, containing the three vertices. (Indeed, there is an explicit construction of the cases when there is no such tree.) As a consequence, we show that there is a polynomial time algorithm to test whether a graph contains a "theta" as an induced subgraph (this was an open question of interest) and an alternative way to test whether a graph contains a "pyramid" (a fundamental step in checking whether a graph is perfect).

Original languageEnglish (US)
Pages (from-to)387-417
Number of pages31
JournalCombinatorica
Volume30
Issue number4
DOIs
StatePublished - Oct 25 2010

All Science Journal Classification (ASJC) codes

  • Discrete Mathematics and Combinatorics
  • Computational Mathematics

Fingerprint Dive into the research topics of 'THE THREE-IN-A-TREE PROBLEM'. Together they form a unique fingerprint.

  • Cite this