Path Kernels and Partitions

Let \(\tau(G)\) denote the number of vertices in a longest path of the graph \(G = (V, E)\). A subset \(K\) of \(V\) is called a \(P_n\)-\emph{kernel} of \(G\) if \(\tau(G[K]) \leq n – 1\) and every vertex \(v \in V(G – K)\) is adjacent to an end-vertex of a path of order \(n – 1\) in \(G[K]\).
A partition \(\{A, B\}\) of \(V\) is called an \((a, b)\)-partition if \(\tau(G[A]) \leq a\) and \(\tau(G[B]) \leq b\).
We show that any graph with girth greater than \(n – 3\) has a \(P_n\)-kernel and that every graph has a \(P_\gamma\)-kernel. As corollaries of these results, we show that if \(\tau(G) = a + b\) and \(G\) has girth greater than \(a – 2\) or \(a \leq 6\), then \(G\) has an \((a, b)\)-partition.