ISSN 1234-3099 (print version)

ISSN 2083-5892 (electronic version)

Discussiones Mathematicae Graph Theory

Journal Impact Factor (JIF 2022): 0.7

5-year Journal Impact Factor (2022): 0.7

CiteScore (2022): 1.9

SNIP (2022): 0.902

Discussiones Mathematicae Graph Theory

Article in volume


X. Zhou

Xiaomin Zhou

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


W. Yang

Weihua Yang

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



X. Guan

Xiaxia Guan

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


C. Qin

Chengfu Qin

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



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



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 ,


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.


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


  1. N. Ananchuen and C. Lewchalermvongs, Internally $4$-connected graphs with no $\{cube,V_{8}\}$-minor, Discuss. Math. Graph Theory 41 (2021) 481–501.
  2. C. Chun, D. Mayhew and J. Oxley, Constructing internally $4$-connected binary matroids, Adv. Appl. Math. 50 (2013) 16–45.
  3. G. Ding, A characterization of graphs with no octahedron minor, J. Graph Theory 74 (2013) 143–162.
  4. G. Ding, C. Lewchalermvongs and J. Maharry, Graphs with no $\overline{P}_7$-minor, Electron. J. Combin. 23(2) (2016) #P2.16.
  5. G. Ding and C. Liu, Excluding a small minor, Discrete Appl. Math. 161 (2013) 355–368.
  6. 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.
  7. Z. Gaslowitz, E.A. Marshall and L. Yepremyan, The characterization of planar, $4$-connected, $K_ {2, 5}$-minor-free graphs (2015).
    arXiv: 1507.06800
  8. H. Hadwiger, Über eine Klassifikation der Streckenkomplexe, Vierteljahresschr. Naturforsch. Ges. Zürich 88 (1943) 133–143.
  9. J. Maharry, A characterization of graphs with no cube minor, J. Combin. Theory Ser. B 80 (2000) 179–201.
  10. J. Maharry, An excluded minor theorem for the octahedron plus an edge, J. Graph Theory 57 (2008) 124–130.
  11. J. Maharry and N. Robertson, The structure of graphs not topologically containing the Wagner graph, J. Combin. Theory Ser. B 121 (2016) 398–420.
  12. N. Martinov, Uncontractable $4$-connected graphs, J. Graph Theory 6 (1982) 343–344.
  13. W.T. Tutte, On the algebraic theory of graph colorings, J. Combin. Theory 1 (1966) 15–50.