Erdős–Gyárfás conjecture for $$P_8$$-free graphs
Erdős–Gyárfás conjecture for $$P_8$$-free graphs
复制标题
ErdÅsâGyárfá 的 $$P_8$$-free 图猜想
DOI：
10.1007/s00373-022-02578-9
复制
发表时间：
2022
影响因子：
0.7
通讯作者：
Shan, Songling
中科院分区：
文献类型：
--
作者：
Gao, Yuping;Shan, Songling
一个图是自由的，如果它不包含与路径8顶点同构的诱导子图。1995年，Erdős和Gyárfás推测，每个最小度数至少为3的图都包含一个周期，其长度是2的幂。本文通过证明在最小度至少为3的每一自由图中存在一个长度为4或8的循环，证实了无图的猜想。
A graph is-free if it contains no induced subgraph isomorphic to the pathon 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-free graphs by showing that there exists a cycle of length four or eight in every-free graph with minimum degree at least three.