Graphs with not all possible path-kernels
type: Item
instance of: scholarly article
title: Graphs with not all possible path-kernels
zbMATH Open document ID: 1066.05107
author: Carsten Thomassen
author: R. E. L. Aldred
published in: Discrete Mathematics
publication date: 2004-08-19T00:00:00Z
review text: 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.
reviewed by: Erich Prisner
Mathematics Subject Classification ID: 05C70
Mathematics Subject Classification ID: 05C38
zbMATH DE Number: 2092842
zbMATH Keywords: path partition conjecture
MaRDI profile type: Publication
full work available at URL: j.disc.2004.02.012
OpenAlex ID: W2026328547
Wikidata QID: Q56926698
cites work: Q4943521
cites work: Q3309863
cites work: Q3701351
cites work: Hypohamiltonian and hypotraceable graphs
DOI: 10.1016/J.DISC.2004.02.012
DBLP publication ID: journals/dm/AldredT04
description: scientific article; zbMATH DE number 2092842