### 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 language | English (US) |
---|---|

Pages (from-to) | 387-417 |

Number of pages | 31 |

Journal | Combinatorica |

Volume | 30 |

Issue number | 4 |

DOIs | |

State | Published - 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

Chudnovsky, M., & Seymour, P. (2010). THE THREE-IN-A-TREE PROBLEM.

*Combinatorica*,*30*(4), 387-417. https://doi.org/10.1007/s00493-010-2334-4