The four-in-a-tree problem in triangle-free graphs (Q844235): Difference between revisions
From MaRDI portal
Removed claim: reviewed by (P1447): Item:Q207731 |
Changed an Item |
||
Property / reviewed by | |||
Property / reviewed by: Ulrich Knauer / rank | |||
Normal rank |
Revision as of 01:41, 11 February 2024
scientific article
Language | Label | Description | Also known as |
---|---|---|---|
English | The four-in-a-tree problem in triangle-free graphs |
scientific article |
Statements
The four-in-a-tree problem in triangle-free graphs (English)
0 references
18 January 2010
0 references
The three-in-a-tree algorithm of \textit{M. Chudnovsky} and \textit{P. Seymour} [``The tree-in-a-tree problem'', Combinatorica (to appear)] decides in time \(O(n ^{4})\) whether three given vertices of a graph belong to an induced tree. Here, four-in-a-tree for triangle-free graphs are studied. The paper answers the question: what does a triangle-free graph look like if no induced tree covers four given vertices? Main Theorem: Let \(G\) be a connected graph with 4 distinct terminals. Then either (1) \(G\) is a cubic or square structure w. r. t. the four terminals, that is \(G\) is a cube or a square with 4 pending vertices, or (2) \(G\) contains an induced tree that covers the four terminals. The authors 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. They 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.
0 references
three-in-a-tree algorithm
0 references
triangle-free graph
0 references
induced tree
0 references