A note on path kernels and partitions

The detour order of a graph G, denoted by τ(G), is the order of a longest path in G. A subset S of V(G) is called a P_n-kernel of G if τ(GS])≤n−1 and every vertex v∈V(G)−S is adjacent to an end-vertex of a path of order n−1 in GS]. A partition of the vertex set of G into two sets, A and B, such that τ(GA])≤a and τ(GB])≤b is called an (a,b)-partition of G. In this paper we show that any graph with girth g has a P_n+1-kernel for every . Furthermore, if τ(G)=a+b, 1≤a≤b, and G has girth greater than , then G has an (a,b)-partition.