Publications

Pancyclicity of 4-connected claw-free bull-free graphs.

Faculty Author(s): Zhan, Mingquan
Student Author(s): -
Department: MATH
Publication: The Australasian Journal of Combinatorics
Year: 2020
Abstract: Let $P_n$ be the path with $n$ vertices, and let $N(i,j,k)$ denote the net obtained by identifying each vertex of a triangle with an endpoint of three disjoint paths $P_{i+1}$, $P_{j+1}$, $P_{k+1}$, respectively. In [J. Graph Theory {\bf 47} (2004), no.~3, 183--202; [msn] MR2089463 [/msn]], R.~J. Gould, T. Łuczak and F. Pfender characterized all pairs of forbidden subgraphs that imply a 3-connected graph is pancyclic. On the other hand, for a 4-connected graph, the following results are known. \par Theorem 1. Every 4-connected $\{ K_{1,3},P_{10} \}$-free graph either is pancyclic or is the line graph of the Petersen graph [M.~J. Ferrara, T. Morris and P.~S. Wenger, J. Graph Theory {\bf 71} (2012), no.~4, 435--447; [msn] MR2988884 [/msn]]. \par Theorem 2. Every 4-connected $\{ K_{1,3},N(8,0,0) \}$-free graph either is pancyclic or is the line graph of the Petersen graph [H.-J. Lai et al., Graphs Combin. {\bf 35} (2019), no.~1, 67--89; [msn] MR3898376 [/msn]]. \par Theorem 3. Every 4-connected $\{ K_{1,3},N(i,j,0) \}$-free graph, where $i+j=6$, is pancyclic [M.~J. Ferrara et al., Discrete Math. {\bf 313} (2013), no.~4, 460--467; [msn] MR3004480 [/msn]]. \par In this paper, the authors prove the following theorem and show that Theorem 4 implies Theorem 3. \par Theorem 4. Every 4-connected $\{ K_{1,3},N(i,j,0) \}$-free graph, where $i+j=7$, either is pancyclic or is the line graph of the Petersen graph.
Link: Pancyclicity of 4-connected claw-free bull-free graphs.