Longest Path and Cycle Transversals in Chordal Graphs

James A. Long, Kevin G. Milans, Michael C. Wigal

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 sh…