A Cycle of Maximum Order in a Graph of High Minimum Degree has a Chord

Daniel John Harvey

Research output: Contribution to journalJournal articleResearchpeer-review

64 Downloads (Pure)

Abstract

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.
Original languageEnglish
Article numberP4.33
JournalThe Electronic Journal of Combinatorics
Volume24
Issue number4
Number of pages8
ISSN1097-1440
Publication statusPublished - 2017

Fingerprint Dive into the research topics of 'A Cycle of Maximum Order in a Graph of High Minimum Degree has a Chord'. Together they form a unique fingerprint.

Cite this