Longest Path and Cycle Transversals in Chordal Graphs

Abstract

We show that if $G$ is a $n$-vertex connected chordal graph, then it admits a longest path transversal of size $O({\log }^{2}n)$. Under the stronger assumption of 2-connectivity, we show $G$ admits a longest cycle transversal of size $O(\log n)$. We also provide longest path and longest cycle transversals which are bounded by the leafage of the chordal graph.

16 pages, 1 figure