Geodesic
Order of the smallest counterexample to Gallai's conjecture
Czechoslovak Mathematical Journal, Tome 68 (2018) no. 2, pp. 341-369 Cet article a éte moissonné depuis la source Czech Digital Mathematics Library

Voir la notice de l'article

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.
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.
DOI : 10.21136/CMJ.2018.0422-16
Classification : 05C38, 05C70, 05C75
Keywords: longest path; matching number 
@article{10_21136_CMJ_2018_0422_16,
     author = {Chen, Fuyuan},
     title = {Order of the smallest counterexample to {Gallai's} conjecture},
     journal = {Czechoslovak Mathematical Journal},
     pages = {341--369},
     year = {2018},
     volume = {68},
     number = {2},
     doi = {10.21136/CMJ.2018.0422-16},
     mrnumber = {3819178},
     zbl = {06890377},
     language = {en},
     url = {http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0422-16/}
}
TY  - JOUR
AU  - Chen, Fuyuan
TI  - Order of the smallest counterexample to Gallai's conjecture
JO  - Czechoslovak Mathematical Journal
PY  - 2018
SP  - 341
EP  - 369
VL  - 68
IS  - 2
UR  - http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0422-16/
DO  - 10.21136/CMJ.2018.0422-16
LA  - en
ID  - 10_21136_CMJ_2018_0422_16
ER  - 
%0 Journal Article
%A Chen, Fuyuan
%T Order of the smallest counterexample to Gallai's conjecture
%J Czechoslovak Mathematical Journal
%D 2018
%P 341-369
%V 68
%N 2
%U http://geodesic.mathdoc.fr/articles/10.21136/CMJ.2018.0422-16/
%R 10.21136/CMJ.2018.0422-16
%G en
%F 10_21136_CMJ_2018_0422_16
Chen, Fuyuan. Order of the smallest counterexample to Gallai's conjecture. Czechoslovak Mathematical Journal, Tome 68 (2018) no. 2, pp. 341-369. doi: 10.21136/CMJ.2018.0422-16

[1] Balister, P., Györi, E., Lehel, J., Schelp, R.: Longest paths in circular arc graphs. Comb. Probab. Comput. 13 (2004), 311-317. | DOI | MR | JFM

[2] Brinkmann, G., Cleemput, N. Van: Private communication.

[3] Chen, F.: Nonempty intersection of longest paths in a graph with a small matching number. Czech. Math. J. 65 (2015), 545-553. | DOI | MR | JFM

[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. | DOI | MR | JFM

[5] Rezende, S. F. de, Fernandes, C. G., Martin, D. M., Wakabayashi, Y.: Intersecting longest paths. Discrete Math. 313 (2013), 1401-1408. | DOI | MR | JFM

[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). | MR | JFM

[7] Klavžar, S., Petkovšek, M.: Graphs with nonempty intersection of longest paths. Ars Comb. 29 (1990), 43-52. | MR | JFM

[8] Petersen, J.: Die Theorie der regulären graphs. Acta Math. 15 (1891), 193-220 German \99999JFM99999 23.0115.03. | DOI | MR

[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. | DOI | MR | JFM

[10] Walther, H., Voss, H. J.: Über Kreise in Graphen. VEB Deutscher Verlag der Wissenschaften, Berlin (1974), German. | MR | JFM

[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. | MR | JFM

[12] Zamfirescu, T. I.: On longest paths and circuits in graphs. Math. Scand. 38 (1976), 211-239. | DOI | MR | JFM

Cité par Sources :