Order of the smallest counterexample to Gallai's conjecture

Czechoslovak Mathematical Journal

Fuyuan Chen¹ 

关键词: longest path;    matching number;   

DOI  :  10.21136/CMJ.2018.0422-16

学科分类：数学（综合）

来源: Akademie Ved Ceske Republiky

【 摘 要 】

  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.

【 授权许可】

Unknown