Article in volume
Authors:
Title:
Linear arboricity of 1-planar graphs
PDFSource:
Discussiones Mathematicae Graph Theory 44(2) (2024) 435-457
Received: 2021-01-31 , Revised: 2022-03-24 , Accepted: 2022-03-29 , Available online: 2022-04-27 , https://doi.org/10.7151/dmgt.2453
Abstract:
The linear arboricity $\textrm{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 $\big\lceil\frac{\Delta(G)}{2}\big\rceil\leq
\textrm{la}(G)\leq\big\lceil\frac{\Delta(G)+1}{2}\big\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 $\Delta(G)\geq13$.
Keywords:
linear arboricity, 1-planar graph, linear coloring, 3-alternating cycle
References:
- J. Akiyama, G. Exoo and F. Harary, Covering and packing in graphs III: Cyclic and acyclic invariants, Math. Slovaca 30 (1980) 405–417.
- 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 - N. Alon, The linear arboricity of graphs, Israel J. Math. 62 (1988) 311–325.
https://doi.org/10.1007/BF02783300 - 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 - 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 - 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 - 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 - 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 - 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 - F. Guldan, Some results on linear arboricity, J. Graph Theory 10 (1986) 505–509.
https://doi.org/10.1002/jgt.3190100408 - 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 - 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 - 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 - 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 - 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 - 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 - 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 - X. Zhang, G. Liu and J. Wu, On the linear arboricity of $1$-planar graphs, Oper. Res. Trans. 3 (2011) 38–44.
- 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
Close