Hitting all longest paths in $H$-free graphs and $H$-graphs

Abstract

The \textit{longest path transversal number} of a connected graph $G$, denoted by $lpt(G)$, is the minimum size of a set of vertices of $G$ that intersects all longest paths in $G$. We present constant upper bounds for the longest path transversal number of \textit{hereditary classes of graphs}, that is, classes of graphs closed under taking induced subgraphs. Our first main result is a structural theorem that allows us to \textit{refine} a given longest path transversal in a graph using domination properties. This has several consequences: First, it implies that for every $t\in \{5,6\}$, every connected $P_t$-free graph $G$ satisfies $lpt(G)\le t-2$. Second, it shows that every $(\text{bull},\text{chair})$-free graph $G$ satisfies $lpt(G)\le 5$. Third, it implies that for every $t\in \mathbb{N}$, every connected chordal graph $G$ with no induced subgraph isomorphic to $K_t \mat \overline{K_t}$ satisfies $lpt(G)\le t-1$, where $K_t \mat \overline{K_t}$ is the graph obtained from a $t$-clique and an independent set of size $t$ by adding a perfect matching between them. Our second main result provides an upper bound for the longest path transversal number in \textit{$H$-intersection graphs}. For a given graph $H$, a graph $G$ is called an \textit{$H$-graph} if there exists a subdivision $H^{\prime }$ of $H$ such that $G$ is the intersection graph of a family of vertex subsets of $H^{\prime }$ that each induce connected subgraphs. The concept of $H$-graphs, introduced by Biró, Hujter, and Tuza, naturally captures interval graphs, circular-arc graphs, and chordal graphs, among others. Our result shows that for every connected graph $H$ with at least two vertices, there exists an integer $k=k(H)$ such that every connected $H$-graph $G$ satisfies $lpt(G)\le k$.