Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
428526 | Information Processing Letters | 2014 | 5 Pages |
Abstract
•We prove the linear arboricity conjecture of embedded graphs.•We can determine the linear arboricity of embedded graphs with Δ⩾9Δ⩾9.•We adopt the “discharging” method in the detailed proof.•Our main results generalize several related known results.
The linear arboricity of a graph G , denoted by la(G)la(G), is the minimum number of linear forest required to partition the edge set E(G)E(G). Akiyama, Exoo and Harary conjectured that ⌈Δ2⌉⩽la(G)⩽⌈Δ+12⌉ for any simple graph G, where Δ is the maximum degree of G. In this paper, it is proved that this conjecture is true for any graph G which can be embedded in a surface of nonnegative Euler characteristic, and furthermore, la(G)=⌈Δ2⌉ if Δ⩾9Δ⩾9.
Related Topics
Physical Sciences and Engineering
Computer Science
Computational Theory and Mathematics
Authors
Huijuan Wang, Jianliang Wu, Bin Liu, Hongyu Chen,