A note on the Path Kernel Conjecture

Let τ ( G ) denote the number of vertices in a longest path in a graph G = ( V , E ) . A subset K of V is called a P n -kernel of G if τ ( G [ K ] ) ≤ n − 1 and every vertex v ∈ V ∖ K is adjacent to an end-vertex of a path of order n − 1 in G [ K ] . It is known that every graph has a P n -kernel for every positive integer n ≤ 9 . R. Aldred and C. Thomassen in [R.E.L. Aldred, C. Thomassen, Graphs with not all possible path-kernels, Discrete Math. 285 (2004) 297–300] proved that there exists a graph which contains no P 364 -kernel. In this paper, we generalise this result. We construct a graph with no P 155 -kernel and for each integer l ≥ 0 we provide a construction of a graph G containing no P τ ( G ) − l -kernel.