Erdős-Gyárfás conjecture on graphs without long induced paths
Fuente:
arXiv
Saved in:
| Main Authors: | , , |
|---|---|
| Format: | Preprint |
| Published: |
2024
|
| Subjects: | |
| Online Access: | |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| _version_ | 1866917918280777728 |
|---|---|
| author | Hegde, Anand Shripad Sandeep, R. B. Shashank, P. |
| author_facet | Hegde, Anand Shripad Sandeep, R. B. Shashank, P. |
| contents | 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_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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_22842 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Erdős-Gyárfás conjecture on graphs without long induced paths Hegde, Anand Shripad Sandeep, R. B. Shashank, P. Combinatorics Data Structures and Algorithms 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_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. |
| title | Erdős-Gyárfás conjecture on graphs without long induced paths |
| topic | Combinatorics Data Structures and Algorithms |
| url | https://arxiv.org/abs/2410.22842 |