Abstract
A graph is \(P_8\)-free if it contains no induced subgraph isomorphic to the path \(P_8\) 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_8\)-free graphs by showing that there exists a cycle of length four or eight in every \(P_8\)-free graph with minimum degree at least three.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
Availability of Data and Material
Not applicable.
References
Chudnovsky, M., Stacho, J.: 3-colorable subclasses of \(P_8\)-free graphs. SIAM J. Discrete Math. 32(2), 1111–1138 (2018)
Daniel, D., Shauger, S.E.: A result on the Erdős–Gyárfás conjecture in planar graphs. In: Proceedings of the Thirty-second Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 153, pp. 129–139. Baton Rouge, LA (2001)
Erdős, P.: Some old and new problems in various branches of combinatorics. Graphs and combinatorics (Marseille, 1995). Discrete Math. 165(166), 227–231 (1997)
Ghaffari, M.H., Mostaghim, Z.: Erdős-Gyárfás conjecture for some families of Cayley graphs. Aequ. Math. 92(1), 1–6 (2018)
Ghasemi, M., Varmazyar, R.: On the Erdős–Gyárfás conjecture for some Cayley graphs. Matematichki Vesnik 73(1), 37–42 (2021)
Heckman, C.C., Krakovski, R.: Erdős–Gyárfás conjecture for cubic planar graphs. Electron. J. Comb. 20(2), 7–43 (2013)
Nowbandegani, P.S., Esfandiari, H., Shirdareh Haghighi, M.H., Bibak, K.: On the Erdős–Gyárfás conjecture in claw-free graphs. Discuss. Math. Graph Theory 34(3), 635–640 (2014)
Shauger, S.E.: Results on the Erdős–Gyárfás conjecture in \(K_{1,m}\)-free graphs. In: Proceedings of the Twenty-ninth Southeastern International Conference on Combinatorics, Graph Theory and Computing, vol. 134, pp. 61–65. Boca Raton (1998)
Acknowledgements
The authors are very grateful to the referees’ careful reading and valuable comments.
Funding
Yuping Gao is partially supported by NSFC (No. 11901263, 12071194, 12271228), NSFC of Gansu Province (No. 20JR5RA229, 21JR7RA511). Songling Shan is supported by NSF grant DMS-2153938.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no conflict of interest.
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
Springer Nature or its licensor holds exclusive rights to this article under a publishing agreement with the author(s) or other rightsholder(s); author self-archiving of the accepted manuscript version of this article is solely governed by the terms of such publishing agreement and applicable law.
About this article
Cite this article
Gao, Y., Shan, S. Erdős–Gyárfás conjecture for \(P_8\)-free graphs. Graphs and Combinatorics 38, 168 (2022). https://doi.org/10.1007/s00373-022-02578-9
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-022-02578-9