Erdős-Gyárfás conjecture on graphs without long induced paths

2024/10/30 by Hegde, Anand Shripad, Sandeep, R. B., Shashank, P.
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #FOS: Computer and information sciences #FOS: Mathematics

paper · doi:10.48550/arxiv.2410.22842

Abstract

Erdős and Gyárfás conjectured in 1994 that every graph with minimum degree at least 3 has a cycle of length a power of 2. In 2022, Gao and Shan (Graphs and Combinatorics) proved that the conjecture is true for P₈-free graphs, i.e., graphs without any induced copies of a path on 8 vertices. In 2024, Hu and Shen (Discrete Mathematics) improved this result by proving that the conjecture is true for P₁₀ -free graphs. With the aid of a computer search, we improve this further by proving that the conjecture is true for P₁₃ -free graphs.

Related

• Erdős-Gyárfás Conjecture for P₁₀-free Graphs
• Erdős-Gyárfás Conjecture for P₈-free graphs
• On the Erdős-Gyárfás conjecture in claw-free graphs
• Cycles of Length 4 or 8 in Graphs with Diameter 2 and Minimum Degree at Least 3
• Longest Cycle above Erdős-Gallai Bound