Summary: A common task in phylogenetics is to find an evolutionary tree representing proximity relationships between species. This motivates the notion of leaf powers: a graph \(G=(V,E)\) is a leaf power if there exist a tree \(T\) on leafset \(V\) and a threshold \(k\) such that \(uv \in E\) if and only if the distance between \(u\) and \(v\) in \(T\) is at most \(k\). Characterizing leaf powers is a challenging open problem, along with determining the complexity of their recognition. Leaf powers are known to be strongly chordal, but few strongly chordal graphs are known to not be leaf powers, as such graphs are difficult to construct. Recently, Nevries and Rosenke asked if leaf powers could be characterized by strong chordality and a finite set of forbidden induced subgraphs.
In this paper, we provide a negative answer to this question, by exhibiting an infinite family \(\mathcal {G}\) of (minimal) strongly chordal graphs that are not leaf powers. During the process, we establish a connection between leaf powers, alternating cycles and quartet compatibility. We also show that deciding if a chordal graph is \(\mathcal {G}\)-free is \(\mathsf {NP}\)-complete.
For the entire collection see [Zbl 1374.68006].