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

Cité par Sources :