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.
- A note on the path Kernel conjecture
- On a tree-partition problem
- Partition problems and kernels of graphs
- A path(ological) partition problem
- scientific article; zbMATH DE number 1416470 (Why is no real title available?)
- A note on a cycle partition problem
- On the Forking Path Conjecture
- The strong path partition conjecture holds for a = 9
- On the strong path partition conjecture
- A note on path kernels and partitions
- The path partition conjecture is true for claw-free graphs
This page was built for publication: Graphs with not all possible path-kernels
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1877673)
