The Linear Arboricity of IC-planar Graphs

Yongjie Li; Haoying Yuan; Juan Liu

doi:10.54691/weh1rn52

Authors

Yongjie Li
Haoying Yuan
Juan Liu

DOI:

https://doi.org/10.54691/weh1rn52

Keywords:

Linear Arboricity; IC-Planar Graph; Linear Coloring; 1-Planar Graph.

Abstract

The linear arboricity of a graph is the minimum number of linear forests that partition the edges of . In 1981, Akiyama, Exoo and Harary conjectured that for any simple graph . A graph is 1-planar if it can be drawn in the plane so that each edge has at most one crossing. An IC-planar graph is a 1-planar graph satisfying the condition that each vertex is incident with at most one crossing edge. It is shown in this paper that every IC-planar graph with maximum degree has .

Downloads

Download data is not yet available.

References

[1] J. Akiyama, G. Exoo and F. Harary:Covering and packing in graphs III: Cyclic and acyclic invariants, athematica Slovaca, Vol. 30 (1980), No.4, p.405--417.

[2] J. Akiyama, G. Exoo and F. Harary:Covering and packing in graphs IV: Linear arboricity, Networks Vol. 11 (1981), p.69--72.

[3] N. Alon:The linear arboricity of graphs, Israel J. Math, Vol. 62 (1988), p.311--325.

[4] M. Cygan, J. Hou, L. Kowalik and B. Lužar, J. Wu:A planar linear arboricity conjecture, J. Graph Theory, Vol. 69 (2012), p.403--425.

[5] H. Enomoto and B. Péroche:The linear arboricity of some regular graphs, J. Graph Theory, Vol. 8 (1984), p.309--324.

[6] A. Ferber, J. Fox and V. Jain:Towards the linear arboricity conjecture, J. Combin. Theory, Ser. B, Vol. 142 (2020), p.56--79.

[7] F. Guldan:Some results on linear arboricity, J. Graph Theory, Vol. 10 (1986), p.505--509.

[8] F. Harary:Covering and Packing in graphs I, Ann. NY Acad. Sci, Vol. 175 (1970), p.198--205.

[9] 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, Vol. 267 (2019), p.120--130.

[10] 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.), Vol. 37 (2021), p.262--278.

[11] J. Wu:On the linear arboricity of planar graphs, J. Graph Theory, Vol. 31 (1999) No. 2 , 129--134.

[12] J.Wu and Y. Wu:The linear arboricity of planar graphs of maximum degree seven is four, J. Graph Theory , Vol. 58 (2008) , p.210--220.

[13] X. Zhang, G. Liu and J. Wu:On the linear arboricity of 1-planar graphs, Oper. Res. Trans, Vol. 3 (2011), p.38--44.28.

[14] J. Wu, J, Hou and X. Sun:A note on the linear arboricity of planar graphs without 4-cycles, ISORA, Vol. 9 (2009), p.174--178.

[15] J. Wu, J. Hou and G. Liu:The linear arboricity of planar graphs with no short cycles, Theoret. Comput. Sci, Vol. 381 (2007), p.230--233.

[16] J. Wu:On the linear arboricity of series-parallel graphs, Graphs Combin, Vol. 16 (2000), p.367--372.

[17] X. Zhang and G. Liu：The structure of plane graphs with independent crossings and its applications to coloring problems, Cent. Eur. J. Math,Vol. 11 (2013), p.308--321.

[18] N. Jiang and D. Huang:Linear arboricity of IC-planar graphs, Acta Math. Appl. Sin, Vol. 46 (2023), p.114--125.

[19] D. Huang and N. Jiang:Linear arboricity of 1-planar graphs, Acta Math.Sinica (Chinese Ser.), Vol. 66 (2023), p.339--352.

[20] J. Liu, X. Hu, D. Zhang and J. kong:The linear 2-arboricity of IC-planar graphs, Discrete Appl.Math, Vol. 338 (2023), p.1--7