Aldred, R. E. L.; Thomassen, Carsten Graphs with not all possible path-kernels. (English) Zbl 1066.05107 Discrete Math. 285, No. 1-3, 297-300 (2004). 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 I. Broere, P. Hajnal and 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. Reviewer: Erich Prisner (Sorengo-Lugano) Cited in 1 ReviewCited in 5 Documents MSC: 05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) 05C38 Paths and cycles Keywords:path partition conjecture Citations:Zbl 0906.05059 PDFBibTeX XMLCite \textit{R. E. L. Aldred} and \textit{C. Thomassen}, Discrete Math. 285, No. 1--3, 297--300 (2004; Zbl 1066.05107) Full Text: DOI References: [1] Broere, I.; Hajnal, P.; Mihók, P., Partition problems and kernels of graphs, Discussiones Mathematicae Graph Theory, 17, 2, 51-56 (1997) [2] Dunbar, J.; Frick, M., Path kernels and partitions, J. Combin. Math. Combin. Comput., 31, 137-149 (1999) · Zbl 0941.05040 [3] J. Dunbar, M. Frick, Path partitions and \(P_n\); J. Dunbar, M. Frick, Path partitions and \(P_n\) · Zbl 0941.05040 [4] P. Hajnal, Graph partitions, Thesis, supervised by L. Lovász, Joszef Attila University, Szeged, Hungary, 1984 (in Hungarian).; P. Hajnal, Graph partitions, Thesis, supervised by L. Lovász, Joszef Attila University, Szeged, Hungary, 1984 (in Hungarian). [5] J.M. Laborde, C. Payan, N.H. Xuong, Independent sets and longest directed paths in digraphs, in: M. Fiedler (Ed.), Graphs and Other Combinatorial Topics, Teubner-Texte Mathematic, Vol. 59, Teubner, Stuttgart, 1983, pp. 173-177.; J.M. Laborde, C. Payan, N.H. Xuong, Independent sets and longest directed paths in digraphs, in: M. Fiedler (Ed.), Graphs and Other Combinatorial Topics, Teubner-Texte Mathematic, Vol. 59, Teubner, Stuttgart, 1983, pp. 173-177. · Zbl 0528.05034 [6] P. Mihók, Problem 4, in: M. Borowiecki, Z. Skupien (Eds.), Graphs, Hypergraphs and Matroids, Zielona Góra, 1985, p. 86.; P. Mihók, Problem 4, in: M. Borowiecki, Z. Skupien (Eds.), Graphs, Hypergraphs and Matroids, Zielona Góra, 1985, p. 86. [7] Thomassen, C., Hypohamiltonian and hypotraceable graphs, Discrete Math., 9, 91-96 (1974) · Zbl 0278.05110 This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.