The four-in-a-tree problem in triangle-free graphs

Nicolas Derhy (), Christophe Picouleau () and Nicolas Trotignon ()
Additional contact information
Nicolas Derhy: CEDRIC, CNAM
Christophe Picouleau: CEDRIC, CNAM
Nicolas Trotignon: Centre d'Economie de la Sorbonne, https://centredeconomiesorbonne.univ-paris1.fr

Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne

Abstract: The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time O(n4) whether three given vertices of a graph belong to an induced tree. Here, we study four-in-a-tree for triangle-free graphs. We give a structural answer to the following question: how does look like a triangle-free graph such that no induced tree covers four given vertices? Our main result says that any such graph must have the "same structure", in a sense to be defined precisely, as a square or a cube. We provide an O(nm)-time algorithm that given a triangle-free graph G together with four vertices outputs either an induced tree that contains them or a partition of V(G) certifying that no such tree exists. We prove that the problem of deciding whether there exists a tree T covering the four vertices such that at most one vertex of T has degree at least 3 is NP-complete

Keywords: three; four; tree; algorithm; 3-in-a-tree; 4-in-a-tree; triangle-free graphs (search for similar items in EconPapers)
Pages: 16 pages
Date: 2008-03
References: Add references at CitEc
Citations:

Downloads: (external link)
ftp://mse.univ-paris1.fr/pub/mse/CES2008/B08023.pdf (application/pdf)

Related works:
This item may be available elsewhere in EconPapers: Search for items with the same title.

Export reference: BibTeX RIS (EndNote, ProCite, RefMan) HTML/Text

Persistent link: https://EconPapers.repec.org/RePEc:mse:cesdoc:b08023

Access Statistics for this paper

More papers in Documents de travail du Centre d'Economie de la Sorbonne from Université Panthéon-Sorbonne (Paris 1), Centre d'Economie de la Sorbonne Contact information at EDIRC.
Bibliographic data for series maintained by Lucie Label ().