1. bookAHEAD OF PRINT
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
access type Open Access

Linear Arboricity of 1-Planar Graphs

Published Online: 27 May 2022
Volume & Issue: AHEAD OF PRINT
Page range: -
Received: 05 Feb 2022
Accepted: 29 Mar 2022
Journal Details
License
Format
Journal
eISSN
2083-5892
First Published
13 Apr 2013
Publication timeframe
4 times per year
Languages
English
Abstract

The linear arboricity la(G) of a graph G is the minimum number of linear forests that partition the edges of G. In 1981, Akiyama, Exoo and Harary conjectured that Δ(G)2 la(G) Δ(G)+12 \left\lceil {{{\Delta \left( G \right)} \over 2}} \right\rceil \le la\left( G \right) \le \left\lceil {{{\Delta \left( G \right) + 1} \over 2}} \right\rceil for any simple graph G. A graph G is 1-planar if it can be drawn in the plane so that each edge has at most one crossing. In this paper, we confirm the conjecture for 1-planar graphs G with Δ(G) ≥ 13.

Keywords

MSC 2010

[1] J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs III: Cyclic and acyclic invariants, Math. Slovaca 30 (1980) 405–417. Search in Google Scholar

[2] J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs IV: Linear arboricity, Networks 11 (1981) 69–72. https://doi.org/10.1002/net.323011010810.1002/net.3230110108 Search in Google Scholar

[3] N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988) 311–325. https://doi.org/10.1007/BF0278330010.1007/BF02783300 Search in Google Scholar

[4] O.V. Borodin, A new proof of the 6 color theorem, J. Graph Theory 19 (1995) 507–521. https://doi.org/10.1002/jgt.319019040610.1002/jgt.3190190406 Search in Google Scholar

[5] O.V. Borodin, A.V. Kostochka, A. Raspaud and E. Sopena, Acyclic colouring of 1-planar graphs, Discrete Appl. Math 114 (2001) 29–41. https://doi.org/10.1016/S0166-218X(00)00359-010.1016/S0166-218X(00)00359-0 Search in Google Scholar

[6] M. Cygan, J.-F. Hou, Ł. Kowalik, B. Lužar and J.-L Wu, A planar linear arboricity conjecture, J. Graph Theory 69 (2012) 403–425. https://doi.org/10.1002/jgt.2059210.1002/jgt.20592 Search in Google Scholar

[7] H. Enomoto and B. Péroche, The linear arboricity of some regular graphs, J. Graph Theory 8 (1984) 309–324. https://doi.org/10.1002/jgt.319008021110.1002/jgt.3190080211 Search in Google Scholar

[8] I. Fabrici and T. Madaras, The structure of 1-planar graphs, Discrete Math. 307 (2007) 854–865. https://doi.org/10.1016/j.disc.2005.11.05610.1016/j.disc.2005.11.056 Search in Google Scholar

[9] A. Ferber, J. Fox and V. Jain, Towards the linear arboricity conjecture, J. Combin. Theory Ser. B 142 (2020) 56–79. https://doi.org/10.1016/j.jctb.2019.08.00910.1016/j.jctb.2019.08.009 Search in Google Scholar

[10] F. Guldan, Some results on linear arboricity, J. Graph Theory 10 (1986) 505–509. https://doi.org/10.1002/jgt.319010040810.1002/jgt.3190100408 Search in Google Scholar

[11] F. Harary, Covering and packing in graphs I, Ann. New York Acad. Sci. 175 (1970) 198–205. https://doi.org/10.1111/j.1749-6632.1970.tb56470.x10.1111/j.1749-6632.1970.tb56470.x Search in Google Scholar

[12] D. Hudák and P. Šugerek, Light edges in 1-planar graphs with prescribed minimum degree, Discuss. Math. Graph Theory 32 (2012) 545–556. https://doi.org/10.7151/dmgt.162510.7151/dmgt.1625 Search in Google Scholar

[13] J. Liu, X. Hu, W. Wang and Y. Wang, Light structures in 1-planar graphs with an application to linear 2-arboricity, Discrete Appl. Math. 267 (2019) 120–130. https://doi.org/10.1016/j.dam.2019.05.00110.1016/j.dam.2019.05.001 Search in Google Scholar

[14] J. Liu, Y. Wang, P. Wang, L. Zhang and W. Wang, An improved upper bound on the linear 2-arboricity of 1-planar graphs, Acta Math. Sin. (Engl. Ser.) 37 (2021) 262–278. https://doi.org/10.1007/s10114-020-9488-910.1007/s10114-020-9488-9 Search in Google Scholar

[15] J.-L. Wu, On the linear arboricity of planar graphs, J. Graph Theory 31 (1999) 129–134. https://doi.org/10.1002/(SICI)1097-0118(199906)31:2¡129::AID-JGT5¿3.0.CO;2-A Search in Google Scholar

[16] J.-L. Wu and Y.-W. Wu, The linear arboricity of planar graphs of maximum degree seven is four, J. Graph Theory 58 (2008) 210–220. https://doi.org/10.1002/jgt.2030510.1002/jgt.20305 Search in Google Scholar

[17] W. Yang, W. Wang and Y. Wang, An improved upper bound for the acyclic chromatic number of 1-planar graphs, Discrete Appl. Math. 283 (2020) 275–291. https://doi.org/10.1016/j.dam.2020.01.01010.1016/j.dam.2020.01.010 Search in Google Scholar

[18] X. Zhang, G. Liu and J. Wu, On the linear arboricity of 1-planar graphs, Oper. Res. Trans. 3 (2011) 38–44. Search in Google Scholar

[19] X. Zhang and J.-L. Wu, On edge colorings of 1-planar graphs, Inform. Process. Lett. 111 (2011) 124–128. https://doi.org/10.1016/j.ipl.2010.11.00110.1016/j.ipl.2010.11.001 Search in Google Scholar

Recommended articles from Trend MD

Plan your remote conference with Sciendo