Czechoslovak Mathematical Journal, Vol. 68, No. 2, pp. 341-369, 2018


Order of the smallest counterexample to Gallai's conjecture

Fuyuan Chen

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.
Keywords:  longest path; matching number
Classification MSC:  05C38, 05C70, 05C75


References:
[1] P. Balister, E. Györi, J. Lehel, R. Schelp: Longest paths in circular arc graphs. Comb. Probab. Comput. 13 (2004), 311-317. DOI 10.1017/S0963548304006145 | MR 2056401 | Zbl 1051.05053
[2] G. Brinkmann, N. Van Cleemput: Private communication.
[3] F. Chen: Nonempty intersection of longest paths in a graph with a small matching number. Czech. Math. J. 65 (2015), 545-553. DOI 10.1007/s10587-015-0193-2 | MR 3360444 | Zbl 1363.05129
[4] G. Chen, J. Ehrenmüller, C. G. Fernandes, C. G. Heise, S. Shan, P. Yang, A. N. Yates: Nonempty intersection of longest paths in series-parallel graphs. Discrete Math. 340 (2017), 287-304. DOI 10.1016/j.disc.2016.07.023 | MR 3584816 | Zbl 1351.05123
[5] S. F. de Rezende, C. G. Fernandes, D. M. Martin, Y. Wakabayashi: Intersecting longest paths. Discrete Math. 313 (2013), 1401-1408. DOI 10.1016/j.disc.2013.02.016 | MR 3061125 | Zbl 1279.05041
[6] T. Gallai: Problem 4. Theory of Graphs. Proceedings of the colloquium held at Tihany, Hungary, September 1966 (eds. P. Erdös, G. Katona), Academic Press, New York (1968). MR 0232693 | Zbl 0155.00201
[7] S. Klavžar, M. Petkovšek: Graphs with nonempty intersection of longest paths. Ars Comb. 29 (1990), 43-52. MR 1046093 | Zbl 0714.05037
[8] J. Petersen: Die Theorie der regulären graphs. Acta Math. 15 (1891), 193-220. (In German.) DOI 10.1007/BF02392606 | MR 1554815 | JFM 23.0115.03
[9] H. Walther: Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen. J. Comb. Theory 6 (1969), 1-6. (In German.) DOI 10.1016/S0021-9800(69)80098-0 | MR 0236054 | Zbl 0184.27504
[10] H. Walther, H. J. Voss: Über Kreise in Graphen. VEB Deutscher Verlag der Wissenschaften, Berlin (1974). (In German.) Zbl 0288.05101
[11] T. I. Zamfirescu: L'histoire et létat présent des bornes connues pour $P_k^j$, $C_k^j$, $\bar{P}_k^j$ et $\bar{C}_k^j$. Cah. Cent. ɉtud. Rech. Opér. 17 (1975), 427-439. (In French.) MR 0401544 | Zbl 0313.05117
[12] T. I. Zamfirescu: On longest paths and circuits in graphs. Math. Scand. 38 (1976), 211-239. DOI 10.7146/math.scand.a-11630 | MR 0429645 | Zbl 0337.05127

Affiliations:   Fuyuan Chen, Anhui University of Finance and Economics, No. 962 Caoshan Road, Bengbu City, P.R. China, e-mail: chenfuyuan19871010@163.com


 
PDF available at: