Graphs with not all possible path-kernels Original Research Article

The Path Partition Conjecture states that the vertices of a graph G with longest path of length c may be partitioned into two parts X and Y such that the longest path in the subgraph of G induced by X has length at most a and the longest path in the subgraph of G induced by Y has length at most b, where a+b=c. Moreover, for each pair a,b such that a+b=c there is a partition with this property. A stronger conjecture by Broere, Hajnal and Mihók, raised as a problem by Mihók in 1985, states the following: For every graph G and each integer k, c⩾k⩾2 there is a partition of V(G) into two parts (K,K̄) such that the subgraph G[K] of G induced by K has no path on more than k−1 vertices and each vertex in K̄ is adjacent to an endvertex of a path on k−1 vertices in G[K]. In this paper we provide a counterexample to this conjecture.