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τ(G[S])≤n - 1 and every vertex v∈V(G) - S is adjacent to an end-vertex of a path of order n - 1 in G[S].A partition of the vertex set of G into two sets, A and B, such thatτ(G[A])≤a andτ(G[B]) < 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 n < (?) - 1.Furthermore, ifτ(G) =a+b,1 (?)(a+1),then G has an (a,b)-partition.