Geodesic
A cycle of maximum order in a graph of high minimum degree has a chord
Daniel J. Harvey1
1DTU Compute Department of Applied Mathematics and Computer Science Technical University of Denmark Lyngby, Denmark
The electronic journal of combinatorics, Tome 24 (2017) no. 4
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

A well-known conjecture of Thomassen states that every cycle of maximum order in a $3$-connected graph contains a chord. While many partial results towards this conjecture have been obtained, the conjecture itself remains unsolved. In this paper, we prove a stronger result without a connectivity assumption for graphs of high minimum degree, which shows Thomassen's conjecture holds in that case. This result is within a constant factor of best possible. In the process of proving this, we prove a more general result showing that large minimum degree forces a large difference between the order of the largest cycle and the order of the largest chordless cycle.
DOI : 10.37236/7152
Classification : 05D10, 05C07, 05C38, 05C35, 05C45
Mots-clés : cycles, minimum degree

Daniel J. Harvey  1

1 DTU Compute Department of Applied Mathematics and Computer Science Technical University of Denmark Lyngby, Denmark 
@article{10_37236_7152,
     author = {Daniel J. Harvey},
     title = {A cycle of maximum order in a graph of high minimum degree has a chord},
     journal = {The electronic journal of combinatorics},
     year = {2017},
     volume = {24},
     number = {4},
     doi = {10.37236/7152},
     zbl = {1376.05160},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/7152/}
}
TY  - JOUR
AU  - Daniel J. Harvey
TI  - A cycle of maximum order in a graph of high minimum degree has a chord
JO  - The electronic journal of combinatorics
PY  - 2017
VL  - 24
IS  - 4
UR  - http://geodesic.mathdoc.fr/articles/10.37236/7152/
DO  - 10.37236/7152
ID  - 10_37236_7152
ER  - 
%0 Journal Article
%A Daniel J. Harvey
%T A cycle of maximum order in a graph of high minimum degree has a chord
%J The electronic journal of combinatorics
%D 2017
%V 24
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/7152/
%R 10.37236/7152
%F 10_37236_7152
Daniel J. Harvey. A cycle of maximum order in a graph of high minimum degree has a chord. The electronic journal of combinatorics, Tome 24 (2017) no. 4. doi: 10.37236/7152

Cité par Sources :