Leaf power

[6] Based on this characterization and similar ones, 3-leaf powers can be recognized in linear time.

[7] Characterizations of 4-leaf powers are given by Rautenbach (2006) and Brandstädt, Le & Sritharan (2008), which also enable linear time recognition.

Recognition of the 5-leaf and 6-leaf power graphs are also solved in linear time by Chang and Ko (2007)[8] and Ducoffe (2018),[9] respectively.

For k ≥ 7 the recognition problem of k-leaf powers was unsolved for a long time, but Lafond (2021) showed that k-leaf powers can be recognized in polynomial time for any fixed k. However, the high dependency on the parameter k makes this algorithm unsuitable for practical use.

Also, it has been proved that recognizing k-leaf powers is fixed-parameter tractable when parameterized by k and the degeneracy of the input graph.