Journal of Combinatorics
Volume 10 (2019)
A new approach towards a conjecture on intersecting three longest paths
Pages: 221 – 234
In 1966, T. Gallai asked whether every connected graph has a vertex that appears in all longest paths. Since then this question has attracted much attention and much work has been done on this topic. One important open question in this area is to ask whether any three longest paths contain a common vertex in a connected graph. It was conjectured that the answer to this question is positive. In this paper, we propose a new approach in view of distances among longest paths in a connected graph, and give a substantial progress towards the conjecture along the idea.
The first author was supported by JSPS KAKENHI (No. 15K04979).
The second author was supported by JSPS KAKENHI (No. 18K13449).
The third author was supported by ANR-17-CE40-0015.
The fourth author was supported by by JST ERATO Grant Number JPMJER1201, Japan and JSPS KAKENHI (No. 18K03391).
Received 19 October 2016
Published 25 January 2019