×

Graphs with not all possible path-kernels. (English) Zbl 1066.05107

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.

MSC:

05C70 Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.)
05C38 Paths and cycles

Citations:

Zbl 0906.05059
PDFBibTeX XMLCite
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.