Longest Cycle above Erdős-Gallai Bound

2022/02/07 by Fomin, Fedor V., Golovach, Petr A., Sagunov, Danil +1
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2202.03061

Abstract

In 1959, Erdős and Gallai proved that every graph G with average vertex degree ad(G)≥ 2 contains a cycle of length at least ad(G). We provide an algorithm that for k≥ 0 in time 2^O(k) n^O(1) decides whether a 2-connected n-vertex graph G contains a cycle of length at least ad(G)+k. This resolves an open problem explicitly mentioned in several papers. The main ingredients of our algorithm are new graph-theoretical results interesting on their own.

Related

• Cycle lengths in sparse graphs
• Cycle lengths and chords under chromatic and degree constraints
• Stability in the Erdos--Gallai Theorem on cycles and paths
• Cycle packing
• Long cycles through prescribed vertices have the Erdős-Pósa property