Erdős-Gyárfás Conjecture for P₈-free graphs

2021/09/03 by Gao, Yuping, Shan, Songling
#Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2109.01277

Abstract

A graph is P₈-free if it contains no induced subgraph isomorphic to the path P₈ on eight vertices. In 1995, Erdős and Gyárfás conjectured that every graph of minimum degree at least three contains a cycle whose length is a power of two. In this paper, we confirm the conjecture for P₈-free graphs by showing that there exists a cycle of length four or eight in every P₈-free graph with minimum degree at least three.

Related

• Erdős-Gyárfás conjecture on graphs without long induced paths
• Erdős-Gyárfás Conjecture for P₁₀-free Graphs
• Cycles of Length 4 or 8 in Graphs with Diameter 2 and Minimum Degree at Least 3
• On the Erdős-Gyárfás conjecture in claw-free graphs
• Graphs without proper subgraphs of minimum degree 3 and short cycles