Journal of Combinatorics

Volume 10 (2019)

Number 2

A new approach towards a conjecture on intersecting three longest paths

Pages: 221 – 234

DOI: https://dx.doi.org/10.4310/JOC.2019.v10.n2.a2

Authors

Shinya Fujita (School of Data Science, Yokohama City University, Kanazawa-ku, Yokohama, Japan)

Michitaka Furuya (College of Liberal Arts and Sciences, Kitasato University, Minami-ku, Sagamihara, Kanagawa, Japan)

Reza Naserasr (CNRS - IRIF UMR 8243, Université Paris Diderot, Paris, France)

Kenta Ozeki (Yokohama National University, Hodogaya-ku, Yokohama, Japan)

Abstract

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.

Full Text (PDF format)

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