×
Gao, Yuping; Shan, Songling

Erdős-Gyárfás conjecture for \(P_8\)-free graphs. (English) Zbl 1498.05142

Graphs Comb. 38, No. 6, Paper No. 168, 7 p. (2022).
Summary: 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.

MSC:

05C35 Extremal problems in graph theory
05C38 Paths and cycles
05C07 Vertex degrees

Keywords:

Erdős-Gyárfás conjecture; \(P_8\)-free graph; cycle

Citations:

Zbl 0872.05020
PDF BibTeX XML Cite
\textit{Y. Gao} and \textit{S. Shan}, Graphs Comb. 38, No. 6, Paper No. 168, 7 p. (2022; Zbl 1498.05142)
Full Text: DOI arXiv

References:

[1] Chudnovsky, M.; Stacho, J., 3-colorable subclasses of \(P_8\)-free graphs, SIAM J. Discrete Math., 32, 2, 1111-1138 (2018) · Zbl 1387.05084
[2] 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) · Zbl 0997.05053
[3] 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) · Zbl 0872.05020
[4] Ghaffari, MH; Mostaghim, Z., Erdős-Gyárfás conjecture for some families of Cayley graphs, Aequ. Math., 92, 1, 1-6 (2018) · Zbl 1489.05080
[5] Ghasemi, M.; Varmazyar, R., On the Erdős-Gyárfás conjecture for some Cayley graphs, Matematichki Vesnik, 73, 1, 37-42 (2021) · Zbl 1474.05221
[6] Heckman, CC; Krakovski, R., Erdős-Gyárfás conjecture for cubic planar graphs, Electron. J. Comb., 20, 2, 7-43 (2013) · Zbl 1267.05152
[7] Nowbandegani, PS; Esfandiari, H.; Shirdareh Haghighi, MH; Bibak, K., On the Erdős-Gyárfás conjecture in claw-free graphs, Discuss. Math. Graph Theory, 34, 3, 635-640 (2014) · Zbl 1295.05135
[8] 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) · Zbl 0952.05038
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.