Order of the smallest counterexample to Gallai's conjecture
Czechoslovak Mathematical Journal (2018)
- Volume: 68, Issue: 2, page 341-369
- ISSN: 0011-4642
Access Full Article
top
Abstract
topHow to cite
topChen, Fuyuan. "Order of the smallest counterexample to Gallai's conjecture." Czechoslovak Mathematical Journal 68.2 (2018): 341-369. <http://eudml.org/doc/294227>.
@article{Chen2018,
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 ^\{\prime \}(G)\le 5$, which implies that Zamfirescu’s conjecture is true.},
author = {Chen, Fuyuan},
journal = {Czechoslovak Mathematical Journal},
keywords = {longest path; matching number},
language = {eng},
number = {2},
pages = {341-369},
publisher = {Institute of Mathematics, Academy of Sciences of the Czech Republic},
title = {Order of the smallest counterexample to Gallai's conjecture},
url = {http://eudml.org/doc/294227},
volume = {68},
year = {2018},
}
TY - JOUR
AU - Chen, Fuyuan
TI - Order of the smallest counterexample to Gallai's conjecture
JO - Czechoslovak Mathematical Journal
PY - 2018
PB - Institute of Mathematics, Academy of Sciences of the Czech Republic
VL - 68
IS - 2
SP - 341
EP - 369
AB - 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 ^{\prime }(G)\le 5$, which implies that Zamfirescu’s conjecture is true.
LA - eng
KW - longest path; matching number
UR - http://eudml.org/doc/294227
ER -
References
top- Balister, P., Györi, E., Lehel, J., Schelp, R., 10.1017/S0963548304006145, Comb. Probab. Comput. 13 (2004), 311-317. (2004) Zbl1051.05053MR2056401DOI10.1017/S0963548304006145
- Brinkmann, G., Cleemput, N. Van, Private communication, .
- Chen, F., 10.1007/s10587-015-0193-2, Czech. Math. J. 65 (2015), 545-553. (2015) Zbl1363.05129MR3360444DOI10.1007/s10587-015-0193-2
- Chen, G., Ehrenmüller, J., Fernandes, C. G., Heise, C. G., Shan, S., Yang, P., Yates, A. N., 10.1016/j.disc.2016.07.023, Discrete Math. 340 (2017), 287-304. (2017) Zbl1351.05123MR3584816DOI10.1016/j.disc.2016.07.023
- Rezende, S. F. de, Fernandes, C. G., Martin, D. M., Wakabayashi, Y., 10.1016/j.disc.2013.02.016, Discrete Math. 313 (2013), 1401-1408. (2013) Zbl1279.05041MR3061125DOI10.1016/j.disc.2013.02.016
- Gallai, T., Problem 4, Theory of Graphs. Proceedings of the colloquium held at Tihany, Hungary, September 1966 P. Erdös, G. Katona Academic Press, New York (1968). (1968) Zbl0155.00201MR0232693
- Klavžar, S., Petkovšek, M., Graphs with nonempty intersection of longest paths, Ars Comb. 29 (1990), 43-52. (1990) Zbl0714.05037MR1046093
- Petersen, J., 10.1007/BF02392606, Acta Math. 15 (1891), 193-220 German 9999JFM99999 23.0115.03. (1891) MR1554815DOI10.1007/BF02392606
- Walther, H., 10.1016/S0021-9800(69)80098-0, J. Comb. Theory 6 (1969), 1-6 German. (1969) Zbl0184.27504MR0236054DOI10.1016/S0021-9800(69)80098-0
- Walther, H., Voss, H. J., Über Kreise in Graphen, VEB Deutscher Verlag der Wissenschaften, Berlin (1974), German. (1974) Zbl0288.05101MR0539852
- Zamfirescu, T. I., L’histoire et l’etat présent des bornes connues pour , , et , Cah. Cent. Étud. Rech. Opér. 17 (1975), 427-439 French. (1975) Zbl0313.05117MR0401544
- Zamfirescu, T. I., 10.7146/math.scand.a-11630, Math. Scand. 38 (1976), 211-239. (1976) Zbl0337.05127MR0429645DOI10.7146/math.scand.a-11630
NotesEmbed ?
topYou must be logged in to post comments.
To embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.