Abstract: A k-leaf power of a tree T, is a graph G whose vertices are the leaves of T and two vertices in G are adjacent if the associated vertices in T have a distance of at most k. A graph is called a leaf power if it is a k-leaf power of a tree for a constant k. Recognition of k-leaf powers, for k at least 5, is still an open problem. In this talk, we show that the recognition of sparse k-leaf powers with bounded degeneracy can be done in linear time.
Joint work with David Eppstein