Geodesic
Linear arboricity of 1-planar graphs
Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 435-457 Cet article a éte moissonné depuis la source Library of Science

Voir la notice de l'article

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⌉ 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: linear arboricity, 1-planar graph, linear coloring, 3-alternating cycle 
@article{DMGT_2024_44_2_a1,
     author = {Wang, Weifan and Liu, Juan and Wang, Yiqiao},
     title = {Linear arboricity of 1-planar graphs},
     journal = {Discussiones Mathematicae. Graph Theory},
     pages = {435--457},
     year = {2024},
     volume = {44},
     number = {2},
     language = {en},
     url = {http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a1/}
}
TY  - JOUR
AU  - Wang, Weifan
AU  - Liu, Juan
AU  - Wang, Yiqiao
TI  - Linear arboricity of 1-planar graphs
JO  - Discussiones Mathematicae. Graph Theory
PY  - 2024
SP  - 435
EP  - 457
VL  - 44
IS  - 2
UR  - http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a1/
LA  - en
ID  - DMGT_2024_44_2_a1
ER  - 
%0 Journal Article
%A Wang, Weifan
%A Liu, Juan
%A Wang, Yiqiao
%T Linear arboricity of 1-planar graphs
%J Discussiones Mathematicae. Graph Theory
%D 2024
%P 435-457
%V 44
%N 2
%U http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a1/
%G en
%F DMGT_2024_44_2_a1
Wang, Weifan; Liu, Juan; Wang, Yiqiao. Linear arboricity of 1-planar graphs. Discussiones Mathematicae. Graph Theory, Tome 44 (2024) no. 2, pp. 435-457. http://geodesic.mathdoc.fr/item/DMGT_2024_44_2_a1/

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

[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.3230110108

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

[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.3190190406

[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-0

[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.20592

[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.3190080211

[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.056

[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.009

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

[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.x

[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.1625

[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.001

[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-9

[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:23.0.CO;2-A

[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.20305

[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.010

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

[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.001