Erdős-Gyárfás Conjecture for P₁₀-free Graphs

2023/08/10 by Zhiquan Hu, Hu, Zhiquan, Changlong Shen +1
Computer Science · Mathematics · #05C38 #05C75 #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics #Graph Labeling and Dimension Problems #Limits and Structures in Graph Theory

paper · pdf · doi:10.48550/arxiv.2308.05675

openalex publication_date 2023/08/10 · openalex created_date 2023/08/18 · openalex updated_date 2026/07/28

Abstract

Let P₁₀ be a path on 10 vertices. A graph is said to be P₁₀-free if it does not contain P₁₀ as an induced subgraph. The well-known Erdős-Gyárfás Conjecture states that every graph with minimum degree at least three has a cycle whose length is a power of 2. In this paper, we show that every P₁₀-free graph with minimum degree at least three contains a cycle of length 4 or 8. This implies that the conjecture is true for P₁₀-free graphs.

Related

• Erdős-Gyárfás conjecture on graphs without long induced paths
• 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
• Graphs without proper subgraphs of minimum degree 3 and short cycles