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 $\bigtriangleup\geq7$ and we have proved that for the two fixed integers $i$, $j\in \{5, 6, 7\}$, if there is no adjacent chordal $i$, $j$-cycles, then the linear arboricity of $G$ is $\lceil\frac\bigtriangleup2\rceil$.}
CHEN Hongling, WANG Huijuan, SUN Fengyan, XUE Juan, GAO Hongwei
. Linear arboricity of planar graphs with maximum degree at least seven[J]. Operations Research Transactions, 2020
, 24(3)
: 154
-160
.
DOI: 10.15960/j.cnki.issn.1007-6093.2020.03.012
[1] Harary F. Covering and packing in graphs I[J]. Annals of the New York Academy of Sciences,1970, 175:198-205.
[2] Akiyama J, Exoo G, Harary Frank. Covering and packing in graphs Ⅲ:cyclic and acyclic invariants[J]. Mathematica Slovaca, 1980, 30(5):405-417.
[3] Jin Akiyama, Geoffrey Exoo, Frank Harary. Covering and packing in graphs IV:Linear arboricity[J]. Networks, 1981, 11:69-72.
[4] Enomoto Hikoe, PWroche Bernard. The linear arboricity of some regular graphs[J]. Graph Theory, 1984, 8:309-324.
[5] Filip Guldan. The linear arboricity of 10 regular graphs[J]. Mathematica Slovaca, 1986, 36:225-228.
[6] Wu J L. Some path decompositions of Halin graphs[J]. Shandong Mining Institute, 1996, 15:219-222.
[7] Wu J L. The linear arboricity of series-parallel graphs[J]. Graphs & Combinatorics, 2000, 16(3):367-372.
[8] Péroche Bernard. Complexity of the linear arboricity of a graph[J]. RAIRO-Operations Research, 1982, 16:125-129.
[9] Alon Noga. The linear arboricity of graphs[J]. Israel Journal of Mathematics,1988, 62(3):311-325.
[10] Alon Noga, Teague V J, Wormald N C. Linear arboricity and linear k-arboricity of regular graphs[J]. Graphs and Combinatorics, 2001, 17:11-16.
[11] AÏt-djafer Houria. Linear arboricity for graphs with multiple edges[J]. Graph Theory, 1987, 11:135-140.
[12] McDiarmid C J H, Reed B A. The linear arboricity of some regular graphs[J]. Random Structure Algorithms, 1990, 1:433-445.
[13] Wu J L. On the linear arboricity of planar graphs[J]. Graph Theory,1999, 31:129-134.
[14] Wu J L, Wu Y W. The linear arboricity of planar graphs of maximum degree seven are four[J]. Graph Theory, 2008, 58:210-220.
[15] Cygan M, Hou J F, Kowalik L, et al. A planar linear arboricity conjecture[J]. Graph Theory, 2012, 69:403-425.
[16] Wang H J, Wu L D, Wu W L, et al. Minimum number of disjoint linear forests covering a planar graph[J]. Journal of Combinatorial Optimization, 2014, 28:274-287.
[17] Wu J L, Hou J F, Sun X Y. A note on the linear arboricity of planar graphs without 4-cycles[J]. ISO-RA, 2009, 09:174-178.
