Geodesic
Non-1-Planarity of Lexicographic Products of Graphs
Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1103-1114.

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

In this paper, we show the non-1-planarity of the lexicographic product of a theta graph and K2. This result completes the proof of the conjecture that a graph G ◦ K2 is 1-planar if and only if G has no edge belonging to two cycles.
Keywords: 1-planar graph, lexicographic product 
@article{DMGT_2021_41_4_a15,
     author = {Matsumoto, Naoki and Suzuki, Yusuke},
     title = {Non-1-Planarity of {Lexicographic} {Products} of {Graphs}},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {1103--1114},
     publisher = {mathdoc},
     volume = {41},
     number = {4},
     year = {2021},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a15/}
}
TY  - JOUR
AU  - Matsumoto, Naoki
AU  - Suzuki, Yusuke
TI  - Non-1-Planarity of Lexicographic Products of Graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2021
SP  - 1103
EP  - 1114
VL  - 41
IS  - 4
PB  - mathdoc
UR  - http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a15/
LA  - en
ID  - DMGT_2021_41_4_a15
ER  - 
%0 Journal Article
%A Matsumoto, Naoki
%A Suzuki, Yusuke
%T Non-1-Planarity of Lexicographic Products of Graphs
%J Discussiones Mathematicae. Graph Theory
%D 2021
%P 1103-1114
%V 41
%N 4
%I mathdoc
%U http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a15/
%G en
%F DMGT_2021_41_4_a15
Matsumoto, Naoki; Suzuki, Yusuke. Non-1-Planarity of Lexicographic Products of Graphs. Discussiones Mathematicae. Graph Theory, Tome 41 (2021) no. 4, pp. 1103-1114. http://geodesic.mathdoc.fr/item/DMGT_2021_41_4_a15/

[1] M.O. Albertson and B. Mohar, Coloring vertices and faces of locally planar graphs, Graphs Combin. 22 (2006) 289–295. https://doi.org/10.1007/s00373-006-0653-4

[2] J. Bucko and J. Czap, 1 -planar lexicographic products of graphs, Appl. Math. Sci. 9 (2015) 5441–5449. https://doi.org/10.12988/ams.2015.56439

[3] J. Czap and D. Hudák, 1 -planarity of complete multipartite graphs, Discrete Appl. Math. 160 (2012) 505–512. https://doi.org/10.1016/j.dam.2011.11.014

[4] J. Czap, D. Hudák and T. Madaras, Joins of 1 -planar graphs, Acta Math. Sin. (Engl. Ser.) 30 (2014) 1867–1876. https://doi.org/10.1007/s10114-014-4017-3

[5] S.G. Kobourov, G. Liotta and F. Montecchiani, An annotated bibliography on 1- planarity, Comput. Sci. Rev. 25 (2017) 49–67. https://doi.org/10.1016/j.cosrev.2017.06.002

[6] V.P. Korzhik, Minimal non- 1 -planar graphs, Discrete Math. 308 (2008) 1319–1327. https://doi.org/10.1016/j.disc.2007.04.009

[7] V.P. Korzhik and B. Mohar, Minimal obstructions for 1 -immersions and hardness of 1 -planarity testing, J. Graph Theory 72 (2013) 30–71. https://doi.org/10.1002/jgt.21630

[8] Y. Suzuki, Re-embeddings of maximum 1 -planar graphs, SIAM J. Discrete Math. 24 (2010) 1527–1540. https://doi.org/10.1137/090746835

[9] C. Yang and J. Xu, Connectivity of lexicographic product and direct product of graphs, Ars Combin. 111 (2013) 3–12.