DMGT

Article in volume

Authors:

X. Zhou

Xiaomin Zhou

Department of Mathematics, Taiyuan University of Technology, Shanxi Taiyuan-030024

email: zxm110700@163.com

W. Yang

Weihua Yang

Department of Mathematics, Taiyuan University of Technology, Shanxi Taiyuan-030024

email: yangweihua@tyut.edu.cn

0000-0002-2786-5173

X. Guan

Xiaxia Guan

School of Mathematical Sciences, Xiamen University, Xiamen, Fujian 361005, P.R. China

email: gxx0544@126.com

C. Qin

Chengfu Qin

School of Mathematics Science, Guangxi Teachers Education University, Nanning, Guangxi 530001, China

email: qtclf@163.com

Title:

A characterization of internally 4-connected $\{P_{10}− \{v_1,v_2\}\}$-minor-free graphs

PDF

Source:

Discussiones Mathematicae Graph Theory 43(3) (2023) 731-742

Received: 2020-09-15 , Revised: 2021-02-17 , Accepted: 2021-02-17 , Available online: 2021-04-21 , https://doi.org/10.7151/dmgt.2404

Abstract:

Let $P_{10}$ be the Petersen graph. Let $V_{8}^{–} =P_{10}-\{v_{1}, v_{2}\}$, where $v_{1}$ and $v_{2}$ are the adjacent vertices of $P_{10}$. In this paper, all internally $4$-connected graphs that do not contain $V_{8}^{–}$ as a minor are charaterized.

Keywords:

internally $4$-connected, $V_{8}^{–}$-minor-free, Petersen graph, $2$-connected minor

References:

N. Ananchuen and C. Lewchalermvongs, Internally $4$-connected graphs with no $\{cube,V_{8}\}$-minor, Discuss. Math. Graph Theory 41 (2021) 481–501.
https://doi.org/10.7151/dmgt.2205
C. Chun, D. Mayhew and J. Oxley, Constructing internally $4$-connected binary matroids, Adv. Appl. Math. 50 (2013) 16–45.
https://doi.org/10.1016/j.aam.2012.03.005
G. Ding, A characterization of graphs with no octahedron minor, J. Graph Theory 74 (2013) 143–162.
https://doi.org/10.1002/jgt.21699
G. Ding, C. Lewchalermvongs and J. Maharry, Graphs with no $\overline{P}_7$-minor, Electron. J. Combin. 23(2) (2016) #P2.16.
https://doi.org/10.37236/5403
G. Ding and C. Liu, Excluding a small minor, Discrete Appl. Math. 161 (2013) 355–368.
https://doi.org/10.1016/j.dam.2012.09.001
M.N. Ellingham, E.A. Marshall, K. Ozeki and S. Tsuchiya, A characterization of $K_{2,4}$-minor-free graphs, SIAM J. Discrete Math 30 (2014) 955–975.
https://doi.org/10.1137/140986517
Z. Gaslowitz, E.A. Marshall and L. Yepremyan, The characterization of planar, $4$-connected, $K_ {2, 5}$-minor-free graphs (2015).
arXiv: 1507.06800
H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljahresschr. Naturforsch. Ges. Zürich 88 (1943) 133–143.
J. Maharry, A characterization of graphs with no cube minor, J. Combin. Theory Ser. B 80 (2000) 179–201.
https://doi.org/10.1006/jctb.2000.1968
J. Maharry, An excluded minor theorem for the octahedron plus an edge, J. Graph Theory 57 (2008) 124–130.
https://doi.org/10.1002/jgt.20272
J. Maharry and N. Robertson, The structure of graphs not topologically containing the Wagner graph, J. Combin. Theory Ser. B 121 (2016) 398–420.
https://doi.org/10.1016/j.jctb.2016.07.011
N. Martinov, Uncontractable $4$-connected graphs, J. Graph Theory 6 (1982) 343–344.
https://doi.org/10.1002/jgt.3190060310
W.T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966) 15–50.
https://doi.org/10.1016/S0021-9800(66)80004-2