| Title:
|
Order of the smallest counterexample to Gallai's conjecture (English) |
| Author:
|
Chen, Fuyuan |
| Language:
|
English |
| Journal:
|
Czechoslovak Mathematical Journal |
| ISSN:
|
0011-4642 (print) |
| ISSN:
|
1572-9141 (online) |
| Volume:
|
68 |
| Issue:
|
2 |
| Year:
|
2018 |
| Pages:
|
341-369 |
| Summary lang:
|
English |
| . |
| Category:
|
math |
| . |
| Summary:
|
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)\leq 5$, which implies that Zamfirescu's conjecture is true. (English) |
| Keyword:
|
longest path |
| Keyword:
|
matching number |
| MSC:
|
05C38 |
| MSC:
|
05C70 |
| MSC:
|
05C75 |
| idZBL:
|
Zbl 06890377 |
| idMR:
|
MR3819178 |
| DOI:
|
10.21136/CMJ.2018.0422-16 |
| . |
| Date available:
|
2018-06-11T10:52:01Z |
| Last updated:
|
2020-07-06 |
| Stable URL:
|
http://hdl.handle.net/10338.dmlcz/147223 |
| . |
| Reference:
|
[1] Balister, P., Györi, E., Lehel, J., Schelp, R.: Longest paths in circular arc graphs.Comb. Probab. Comput. 13 (2004), 311-317. Zbl 1051.05053, MR 2056401, 10.1017/S0963548304006145 |
| Reference:
|
[2] Brinkmann, G., Cleemput, N. Van: Private communication.. |
| Reference:
|
[3] Chen, F.: Nonempty intersection of longest paths in a graph with a small matching number.Czech. Math. J. 65 (2015), 545-553. Zbl 1363.05129, MR 3360444, 10.1007/s10587-015-0193-2 |
| Reference:
|
[4] Chen, G., Ehrenmüller, J., Fernandes, C. G., Heise, C. G., Shan, S., Yang, P., Yates, A. N.: Nonempty intersection of longest paths in series-parallel graphs.Discrete Math. 340 (2017), 287-304. Zbl 1351.05123, MR 3584816, 10.1016/j.disc.2016.07.023 |
| Reference:
|
[5] Rezende, S. F. de, Fernandes, C. G., Martin, D. M., Wakabayashi, Y.: Intersecting longest paths.Discrete Math. 313 (2013), 1401-1408. Zbl 1279.05041, MR 3061125, 10.1016/j.disc.2013.02.016 |
| Reference:
|
[6] 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). Zbl 0155.00201, MR 0232693 |
| Reference:
|
[7] Klavžar, S., Petkovšek, M.: Graphs with nonempty intersection of longest paths.Ars Comb. 29 (1990), 43-52. Zbl 0714.05037, MR 1046093 |
| Reference:
|
[8] Petersen, J.: Die Theorie der regulären graphs.Acta Math. 15 (1891), 193-220 German \99999JFM99999 23.0115.03. MR 1554815, 10.1007/BF02392606 |
| Reference:
|
[9] Walther, H.: Über die Nichtexistenz eines Knotenpunktes, durch den alle längsten Wege eines Graphen gehen.J. Comb. Theory 6 (1969), 1-6 German. Zbl 0184.27504, MR 0236054, 10.1016/S0021-9800(69)80098-0 |
| Reference:
|
[10] Walther, H., Voss, H. J.: Über Kreise in Graphen.VEB Deutscher Verlag der Wissenschaften, Berlin (1974), German. Zbl 0288.05101, MR 0539852 |
| Reference:
|
[11] Zamfirescu, T. I.: L'histoire et l'etat 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 French. Zbl 0313.05117, MR 0401544 |
| Reference:
|
[12] Zamfirescu, T. I.: On longest paths and circuits in graphs.Math. Scand. 38 (1976), 211-239. Zbl 0337.05127, MR 0429645, 10.7146/math.scand.a-11630 |
| . |
