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

  • Daniel J. Harvey
Keywords: Graph theory, Cycles, Minimum degree

Abstract

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.
Published
2017-11-24
Article Number
P4.33