最大度大于等于7的平面图的线性荫度

Linear arboricity of planar graphs with maximum degree at least seven

图的染色问题在组合优化、计算机科学和Hessians矩阵的网络计算等方面具有非常重要的应用。其中图的染色中有一种重要的染色——线性荫度,它是一种非正常的边染色,即在简单无向图中,它的边可以分割成线性森林的最小数量。研究最大度△(G)≥7的平面图G的线性荫度,证明了对于两个固定的整数i,j∈{5,6,7},如果图G中不存在相邻的含弦i,j-圈,则图G的线性荫度为[△/2]。

Graph coloring has interesting real-life applications in optimization,computer science and network design,such as file transferring in a computer network,computation of Hessians matrix and so on.There is an important coloring in the coloring of the graph,linear arboricity,which is an improper edge coloring,and the linear arboricity of an undirected graph is the smallest number of linear forests whose edges can be partitioned into.In this paper,we mainly studied linear arboricity on planar graphs with maximum degree△≥7 and we have proved that for the two fixed integers i,j∈{5,6,7},if there is no adjacent chordal i,j-cycles,then the linear arboricity of G is[△/2].