The four-in-a-tree problem in triangle-free graphs (Q844235): Difference between revisions
From MaRDI portal
Created a new Item |
ReferenceBot (talk | contribs) Changed an Item |
||
(6 intermediate revisions by 5 users not shown) | |||
Property / reviewed by | |||
Property / reviewed by: Ulrich Knauer / rank | |||
Property / reviewed by | |||
Property / reviewed by: Ulrich Knauer / rank | |||
Normal rank | |||
Property / MaRDI profile type | |||
Property / MaRDI profile type: MaRDI publication profile / rank | |||
Normal rank | |||
Property / OpenAlex ID | |||
Property / OpenAlex ID: W3099919903 / rank | |||
Normal rank | |||
Property / arXiv ID | |||
Property / arXiv ID: 1309.0978 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: On the complexity of testing for odd holes and induced odd paths / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q5421811 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: The three-in-a-tree problem / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Q3684121 / rank | |||
Normal rank | |||
Property / cites work | |||
Property / cites work: Detecting induced subgraphs / rank | |||
Normal rank | |||
links / mardi / name | links / mardi / name | ||
Latest revision as of 09:01, 2 July 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