Erd\H{o}s-Gy\'arf\'as conjecture on graphs without long induced paths

Autor:	Hegde, Anand Shripad, Sandeep, R. B., Shashank, P.
Rok vydání:	2024
Předmět:	Mathematics - Combinatorics Computer Science - Data Structures and Algorithms
Druh dokumentu:	Working Paper
Popis:	In 1994, Erd\H{o}s and Gy\'arf\'as conjectured 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_8$-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_{10}$-free graphs. With the aid of a computer search, we improve this further by proving that the conjecture is true for $P_{13}$-free graphs. Comment: 5 pages
Databáze:	arXiv
Externí odkaz:	http://arxiv.org/abs/2410.22842 Zobrazit plný text záznamu View this record from Arxiv