Longest Cycle Above Erdös-Gallai Bound
Journal article, Peer reviewed
Published version
View/ Open
Date
2022Metadata
Show full item recordCollections
- Department of Informatics [922]
- Registrations from Cristin [9558]
Original version
Leibniz International Proceedings in Informatics. 2022, 244, 55:1-55:15. https://doi.org/10.4230/LIPIcs.ESA.2022.55Abstract
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^𝒪(k)⋅n^𝒪(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.