Graphs with not all possible path-kernels (Q1877673): Difference between revisions

Let \(\tau(G)\) denote the number of vertices in a longest path in a graph \(G\). The path partition conjecture states that for every graph \(G\) and for all integers \(a\) and \(b\) with \(a+ b= \tau(G)\) there is a partition \(\{A, B\}\) of the vertex set of \(G\) such that \(\tau(G[A])\leq a\) and \(\tau(G[B])\leq b\). Even stronger is the following conjecture by \textit{I. Broere}, \textit{P. Hajnal} and \textit{P. Mihók} [Discuss. Math., Graph Theory 17, No. 2, 311--313 (1997; Zbl 0906.05059)], stating that for every graph \(G\) and for every integer \(k\), \(2\leq k\leq \tau(G)\), there is a partition \(\{A, B\}\) of the vertex set of \(G\) such that \(\tau(G[A])= k- 1\) and each vertex in \(B\) is adjacent to an end vertex of a longest path (on \(k- 1\) vertices) in \(G[A]\). The paper disproves Broere, Hajnal and Mihók's conjecture by giving a counterexample with 364 vertices.