Non-empty intersection of longest paths in $H$-free graphs

Abstract

We make progress toward a characterization of the graphs $H$ such that every connected $H$-free graph has a longest path transversal of size $1$. In particular, we show that the graphs $H$ on at most $4$ vertices satisfying this property are exactly the linear forests. We also show that if the order of a connected graph $G$ is large relative to its connectivity $\kappa (G)$, and its independence number $\alpha (G)$ satisfies $\alpha (G)\le \kappa (G)+2$, then each vertex of maximum degree forms a longest path transversal of size $1$.

A previous arXiv post (arXiv:2005.02716) has been split into two parts; this is the second part

References in corpus (3)

• Sublinear Longest Path Transversals
• Nonempty intersection of longest paths in $2K_2$-free graphs
• Nonempty intersection of longest paths in graphs without forbidden pairs