Journal article
A Cycle of Maximum Order in a Graph of High Minimum Degree has a Chord
A well-known conjecture of Thomassen states that every cycle of maximum order in a 33-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.
Language: | English |
---|---|
Publisher: | The Electronic Journal of Combinatorics |
Year: | 2017 |
ISSN: | 10778926 and 10971440 |
Types: | Journal article |
DOI: | 10.37236/7152 |