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

Publication: Research - peer-reviewJournal article – Annual report year: 2017

Documents

View graph of relations

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
ISSN1077-8926
StatePublished - 2017
Download as:
Download as PDF
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
PDF
Download as HTML
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
HTML
Download as Word
Select render style:
APAAuthorCBE/CSEHarvardMLAStandardVancouverShortLong
Word

ID: 140634790