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

Nicolas Derhy, Christophe Picouleau, Nicolas Trotignon

The three-in-a-tree algorithm of Chudnovsky and Seymour decides in time $O(n^4)$ whether three given vertices of a graph belong to an induced tree. Here, we study four-in-a-tree fo…