Article in press
Authors:
Weihua Yang
Department of Mathematics, Taiyuan University of Technology, Shanxi Taiyuan-030024
email: yangweihua@tyut.edu.cn
Title:
The excluded minor theorem for the Petersen graph contracting exactly two edges of a perfect matching and one other edge
PDFSource:
Discussiones Mathematicae Graph Theory
Received: 2025-01-16 , Revised: 2025-05-11 , Accepted: 2025-05-13 , Available online: 2025-06-20 , https://doi.org/10.7151/dmgt.2589
Abstract:
In order to characterize graphs which do not contain the Petersen graph as a
minor, several authors explore characterizations of graphs which do not contain
some minors of the Petersen graph. By symmetry, there are three minors that can be
obtained from the Petersen graph by contracting exactly two edges of a perfect
matching and one other edge. Let $P_1$, $P_2$ and $P_3$ be the three graphs.
In this article, we characterize all 4-connected $P_i$-minor-free graphs for
$i=1, 2, 3$.
Keywords:
forbidden minor, 4-connected graph, Petersen graph
References:
- G. Ding, C. Lewchalermvongs and J. Maharry, Graphs with no $\bar P_7 $-minor, Electron. J. Combin. 23 (2016) # P2.16.
https://doi.org/10.37236/5403 - A.B. Ferguson, Excluding Two Minors of the Petersen Graph, PhD Thesis (Louisiana State University, 2015).
https://doi.org/10.31390/gradschool_dissertations.63 - W. Jia, S. Kou, W. Yang and C. Qin, A Note on $Oct_1^+$-minor-free graphs and $Oct_2^+$-minor-free graphs, J. Interconnect. Netw. 22(4) (2022) 2150030.
https://doi.org/10.1142/S0219265921500304 - J. Maharry, An excluded minor theorem for the octahedron, J. Graph Theory 31 (1999) 95–100.
https://doi.org/10.1002/(SICI)1097-0118(199906)31:2<95::AID-JGT2>3.3.CO;2-E - N. Martinov, Uncontractable $4$-connected graphs, J. Graph Theory 6 (1982) 343–344.
https://doi.org/10.1002/jgt.3190060310 - C. Qin and G. Ding, A chain theorem for $4$-connected graphs, J. Combin. Theory Ser. B 134 (2019) 341–349.
https://doi.org/10.1016/j.jctb.2018.07.005
Close