$k$-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for $k \geq 5$
<|reference_start|>$k$-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden Induced Subgraphs for $k \geq 5$: A graph $G=(V,E)$ is a $k$-leaf power if there is a tree $T$ whose leaves are the vertices of $G$ with the property that a pair of leaves $u$ and $v$ induce an edge in $G$ if and only if they are distance at most $k$ apart in $T$. For $k\le 4$, it is known that there exists a finite set $F_k$ of graphs such that the class $L(k)$ of $k$-leaf power graphs is characterized as the set of strongly chordal graphs that do not contain any graph in $F_k$ as an induced subgraph. We prove no such characterization holds for $k\ge 5$. That is, for any $k\ge 5$, there is no finite set $F_k$ of graphs such that $L(k)$ is equivalent to the set of strongly chordal graphs that do not contain as an induced subgraph any graph in $F_k$.<|reference_end|>
@article{la tour2024$k$-leaf,
    title={$k$-Leaf Powers Cannot be Characterized by a Finite Set of Forbidden
  Induced Subgraphs for $k \geq 5$},
    author={Max Dupr'e la Tour, Manuel Lafond, Ndiam'e Ndiaye, Adrian Vetta},
    journal={arXiv preprint arXiv:2407.02412},
    year={2024},
    archivePrefix={arXiv},
    eprint={2407.02412},
    primaryClass={math.CO cs.DM}
}