Geodesic
The matching extendability of 7-connected maximal 1-plane graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 777-790 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

A graph is 1-planar if it can be drawn in the plane such that each edge is crossed at most once. A graph, together with a 1-planar drawing is called 1-plane. A graph is said to be k (≥ 1)-extendable if every matching of size k can be extended to a perfect matching. It is known that the vertex connectivity of a 1-plane graph is at most 7. In this paper, we characterize the k-extendability of 7-connected maximal 1-plane graphs. We show that every 7-connected maximal 1-plane graph with even order is k-extendable for 1≤ k≤ 3. And any 7-connected maximal 1-plane graph is not k-extendable for 4≤ k≤ 11. As for k≥ 12, any 7-connected maximal 1-plane graph with n vertices is not k-extendable unless n=2k.
Keywords: perfect matching, 7-connected maximal $1$-plane graph, matching extendability 
@article{DMGT_2024_44_2_a18,
     author = {Huang, Yuanqiu and Zhang, Licheng and Wang, Yuxi},
     title = {The matching extendability of 7-connected maximal 1-plane graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {777--790},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a18/}
}
TY  - JOUR
AU  - Huang, Yuanqiu
AU  - Zhang, Licheng
AU  - Wang, Yuxi
TI  - The matching extendability of 7-connected maximal 1-plane graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 777
EP  - 790
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a18/
LA  - en
ID  - DMGT_2024_44_2_a18
ER  - 
%0 Journal Article
%A Huang, Yuanqiu
%A Zhang, Licheng
%A Wang, Yuxi
%T The matching extendability of 7-connected maximal 1-plane graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 777-790
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a18/
%G en
%F DMGT_2024_44_2_a18
Huang, Yuanqiu; Zhang, Licheng; Wang, Yuxi. The matching extendability of 7-connected maximal 1-plane graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 777-790. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a18/

[1] R.E.L. Aldred and M.D. Plummer, Edge proximity and matching extension in planar triangulations, Australas. J. Combin. 29 (2004) 215–224.

[2] C. Bachmaier, F.J. Brandenburg, K. Hanauer, D. Neuwirth and J. Reislhuber, NIC}-planar graphs, Discrete Appl. Math. 232 (2017) 23–40. https://doi.org/10.1016/j.dam.2017.08.015

[3] J. Barát and G. Tóth, Improvements on the density of maximal 1-planar graphs, J. Graph Theory 88 (2018) 101–109. https://doi.org/10.1002/jgt.22187

[4] I. Baybars, On k-path hamiltonian maximal planar graphs, Discrete Math. 40 (1982) 119–121. https://doi.org/10.1016/0012-365X(82)90193-5

[5] T. Biedl, Are highly connected 1-planar graphs Hamiltonian? (2019). arXiv: 1911.02153

[6] T. Biedl, A note on 1-planar graphs with minimum degree 7, Discrete Appl. Math. 289 (2021) 230–232. https://doi.org/10.1016/j.dam.2020.10.004

[7] T. Biedl and J. Wittnebel, Matchings in 1-planar graphs with large minimum degree, J. Graph Theory 99 (2022) 217–230. https://doi.org/10.1002/jgt.22736

[8] R. Bodendiek, H. Schumacher and K. Wagner, Über 1-optimale {Graphen}, Math. Nachr. 117(1) (1984) 323–339. https://doi.org/10.1002/mana.3211170125

[9] W. Didimo, Density of straight-line 1-planar graph drawings, Inform. Process. Lett. 113(7) (2013) 236–240. https://doi.org/10.1016/j.ipl.2013.01.013

[10] P. Eades, S.-H. Hong, N. Katoh, G. Liotta, P. Schweitzer and Y. Suzuki, A linear time algorithm for testing maximal 1-planarity of graphs with a rotation system, Theoret. Comput. Sci. 513 (2013) 65–76. https://doi.org/10.1016/j.tcs.2013.09.029

[11] I. Fabrici, J. Harant, T. Madaras, S. Mohr, R. Soták and C.T. Zamfirescu, Long cycles and spanning subgraphs of locally maximal 1-planar graphs, J. Graph Theory 95 (2020) 125–137. https://doi.org/10.1002/jgt.22542

[12] J. Fujisawa, K. Segawa and Y. Suzuki, The matching extendability of optimal 1-planar graphs, Graphs Combin. 34 (2018) 1089–1099. https://doi.org/10.1007/s00373-018-1932-6

[13] J.P. Gollin, K. Hendrey, A. Methuku, C. Tompkins and X. Zhang, Counting cliques in 1-planar graphs (2021). arXiv: 2109.02906

[14] A. Grigoriev and H.L. Bodlaender, Algorithms for graphs embeddable with few crossings per edge, Algorithmica 49 (2007) 1–11. https://doi.org/10.1007/s00453-007-0010-x

[15] J. Hopcroft and R. Tarjan, Efficient planarity testing, J. ACM 21 (1974) 549–568. https://doi.org/10.1145/321850.321852

[16] D. Hudák, T. Madaras and Y. Suzuki, On properties of maximal 1-planar graphs, Discuss. Math. Graph Theory 32 (2012) 737–747. https://doi.org/10.7151/dmgt.1639

[17] F. István, On straight-line representation of planar graphs, Acta Univ. Szeged. Sect. Sci. Math. 11 (1948) 229–233.

[18] 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

[19] 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

[20] Z. Ouyang, Y. Huang and F. Dong, The maximal 1-planarity and crossing numbers of graphs, Graphs Combin. 37 (2021) 1333–1344. https://doi.org/10.1007/s00373-021-02320-x

[21] J. Pach and G. Tóth, Graphs drawn with few crossings per edge, Combinatorica 17 (1997) 427–439. https://doi.org/10.1007/BF01215922

[22] M.D. Plummer, A theorem on matchings in the plane, Ann. Discrete Math. 41 (1988) 347–354. https://doi.org/10.1016/S0167-5060(08)70473-4

[23] M.D. Plummer, On n-extendable graphs, Discrete Math. 31 (1980) 201–210. https://doi.org/10.1016/0012-365X(80)90037-0

[24] M.D. Plummer, Extending matchings in planar graphs IV}, Discrete Math. 109 (1992) 207–219. https://doi.org/10.1016/0012-365X(92)90292-N

[25] G. Ringel, Ein Sechsfarbenproblem auf der Kugel, Abh. Math. Semin. Univ. Hambg. 29 (1965) 107–117. https://doi.org/10.1007/BF02996313

[26] Y. Suzuki, \textrm{1-Planar Graphs}, in: Beyond Planar Graphs, S.-H. Hong and T. Tokuyama (Ed(s)), (Springer 2020) 47–68. https://doi.org/10.1007/978-981-15-6533-5_4

[27] R. Thomas and X.X. Yu, 4-connected projective-planar graphs are Hamiltonian, J. Combin. Theory Ser. B 62 (1994) 114–132. https://doi.org/10.1006/jctb.1994.1058

[28] W. Yang, Y. Wang, W. Wang and K.-W. Lih, IC}-planar graphs are 6-choosable, SIAM J. Discrete Math. 35 (2021) 1729–1745. https://doi.org/10.1137/20M133261X

[29] X. Zhang, H.-J. Wang and L. Xu, Equitable coloring of three classes of 1-planar graphs, Acta Math. Appl. Sin. Engl. Ser. 34 (2018) 362–372. https://doi.org/10.1007/s10255-018-0752-z