Path cover asks, what is the minimal number k such that G can be covered by k vertex-disjoint paths. (Path cover of G has size 1 if and only if G has a Hamiltonian path).
Is there a graph class (especially, I am looking for hereditary one), where Hamiltonian path problem can be solved in polynomial time but deciding the size of path cover is NP-hard? Or is there any reason why such class does not exist?