Geodesic
Internally 4-Connected Graphs with No {Cube, V8}-Minor
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 481-501.

Voir la notice de l'article provenant de la source Library of Science

A simple graph is a minor of another if the first is obtained from the second by deleting vertices, deleting edges, contracting edges, and deleting loops and parallel edges that are created when we contract edges. A cube is an internally 4-connected planar graph with eight vertices and twelve edges corresponding to the skeleton of the cube in the platonic solid, and the Wagner graph V8 is an internally 4-connected nonplanar graph obtained from a cube by introducing a twist. A complete characterization of all internally 4-connected graphs with no V8 minor is given in J. Maharry and N. Robertson, The structure of graphs not topologically containing the Wagner graph, J. Combin. Theory Ser. B 121 (2016) 398–420; on the other hand, only a characterization of 3-connected graphs with no cube minor is given in J. Maharry, A characterization of graphs with no cube minor, J. Combin. Theory Ser. B 80 (2008) 179–201. In this paper we determine all internally 4-connected graphs that contain neither cube nor V8 as minors. This result provides a step closer to a complete characterization of all internally 4-connected graphs with no cube minor.
Keywords: internally 4-connected, minor, cube graph, V8 graph 
@article{DMGT_2021_41_2_a9,
     author = {Lewchalermvongs, Chanun and Ananchuen, Nawarat},
     title = {Internally {4-Connected} {Graphs} with {No} {{Cube,} {V\protect\textsubscript{8}}-Minor}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {481--501},
     publisher = {mathdoc},
     volume = {41},
     number = {2},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a9/}
}
TY  - JOUR
AU  - Lewchalermvongs, Chanun
AU  - Ananchuen, Nawarat
TI  - Internally 4-Connected Graphs with No {Cube, V8}-Minor
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 481
EP  - 501
VL  - 41
IS  - 2
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a9/
LA  - en
ID  - DMGT_2021_41_2_a9
ER  - 
%0 Journal Article
%A Lewchalermvongs, Chanun
%A Ananchuen, Nawarat
%T Internally 4-Connected Graphs with No {Cube, V8}-Minor
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 481-501
%V 41
%N 2
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a9/
%G en
%F DMGT_2021_41_2_a9
Lewchalermvongs, Chanun; Ananchuen, Nawarat. Internally 4-Connected Graphs with No {Cube, V8}-Minor. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 2, pp. 481-501. http://geodesic.mathdoc.fr/item/DMGT_2021_41_2_a9/

[1] C. Chun, D. Mayhew and J. Oxley, Constructing internally 4-connected binary matroids, Adv. Appl. Math. 50 (2013) 16–45. doi:10.1016/j.aam.2012.03.005

[2] R. Diestel, Graph Theory (Springer Heidelberg Dordrecht London New York, 2010).

[3] G. Ding, A characterization of graphs with no octahedron minor, J. Graph Theory 74 (2013) 143–162. doi:10.1002/jgt.21699

[4] G. Ding and C. Liu, Excluding a small minor, Discrete Appl. Math. 161 (2013) 355–368. doi:10.1016/j.dam.2012.09.001

[5] G. Ding, C. Lewchalermvongs and J. Maharry, Graphs with no $\overline{P}_7$-minor, Electron. J. Combin. 23 (2016) #P2.16.

[6] J. Maharry, An excluded minor theorem for the octahedron, J. Graph Theory 31 (1999) 95–100. doi:10.1002/(SICI)1097-0118(199906)31:2〈95::AID-JGT2〉3.0.CO;2-N

[7] J. Maharry, A characterization of graphs with no cube minor, J. Combin. Theory Ser. B 80 (2008) 179–201. doi:10.1006/jctb.2000.1968

[8] J. Maharry, An excluded minor theorem for the octahedron plus an edge, J. Graph Theory 57 (2008) 124–130. doi:10.1002/jgt.20272

[9] J. Maharry and N. Robertson, The structure of graphs not topologically containing the Wagner graph, J. Combin. Theory Ser. B 121 (2016) 398–420. doi:10.1016/j.jctb.2016.07.011