THE THREE-IN-A-TREE PROBLEM

Maria Chudnovsky; Paul Seymour

doi:10.1007/s00493-010-2334-4

THE THREE-IN-A-TREE PROBLEM

Maria Chudnovsky, Paul Seymour

Mathematics

Research output: Contribution to journal › Article › peer-review

50 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 language	English (US)
Pages (from-to)	387-417
Number of pages	31
Journal	Combinatorica
Volume	30
Issue number	4
DOIs	https://doi.org/10.1007/s00493-010-2334-4
State	Published - 2010

All Science Journal Classification (ASJC) codes

Discrete Mathematics and Combinatorics
Computational Mathematics

Access to Document

10.1007/s00493-010-2334-4

Cite this

@article{f5730c9dd7994d019a5aef414ec2c49e,

title = "THE THREE-IN-A-TREE PROBLEM",

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).",

author = "Maria Chudnovsky and Paul Seymour",

note = "Funding Information: * This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. † Supported by ONR grant N00014-01-1-0608, and NSF grant DMS-0070912.",

year = "2010",

doi = "10.1007/s00493-010-2334-4",

language = "English (US)",

volume = "30",

pages = "387--417",

journal = "Combinatorica",

issn = "0209-9683",

publisher = "Janos Bolyai Mathematical Society",

number = "4",

}

TY - JOUR

T1 - THE THREE-IN-A-TREE PROBLEM

AU - Chudnovsky, Maria

AU - Seymour, Paul

N1 - Funding Information: * This research was conducted while the author served as a Clay Mathematics Institute Research Fellow. † Supported by ONR grant N00014-01-1-0608, and NSF grant DMS-0070912.

PY - 2010

Y1 - 2010

N2 - 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).

AB - 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).

UR - http://www.scopus.com/inward/record.url?scp=77958053510&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=77958053510&partnerID=8YFLogxK

U2 - 10.1007/s00493-010-2334-4

DO - 10.1007/s00493-010-2334-4

M3 - Article

AN - SCOPUS:77958053510

SN - 0209-9683

VL - 30

SP - 387

EP - 417

JO - Combinatorica

JF - Combinatorica

IS - 4

ER -

THE THREE-IN-A-TREE PROBLEM

Abstract

All Science Journal Classification (ASJC) codes

Access to Document

Other files and links

Fingerprint

Cite this