Czechoslovak Mathematical Journal, first online, pp. 1-29
Order of the smallest counterexample to Gallai's conjecture
Received August 7, 2016. First published February 7, 2018.
Abstract: In 1966, Gallai conjectured that all the longest paths of a connected graph have a common vertex. Zamfirescu conjectured that the smallest counterexample to Gallai's conjecture is a graph on 12 vertices. We prove that Gallai's conjecture is true for every connected graph $G$ with $\alpha'(G)\leq5$, which implies that Zamfirescu's conjecture is true.