标题:On the linear arboricity of graphs embeddable in surfaces
作者:Huijuan Wang;Jianliang Wu;Bin Liu;Hongyu Chen
作者机构:[Wang, H] School of Mathematics, Shandong University, Jinan, 250100, China;[ Wu, J] School of Mathematics, Shandong University, Jinan, 250100, China;[ 更多
通讯作者:Liu, B
通讯作者地址:[Liu, B]Ocean Univ China, Dept Math, Qingdao 266100, Peoples R China.
来源:Information processing letters
出版年:2014
卷:114
期:9
页码:475-479
DOI:10.1016/j.ipl.2014.03.013
关键词:Combinatorial problems;Euler characteristic;Linear arboricity;Embedded graph
摘要:The linear arboricity of a graph G, denoted by la(G), is the minimum number of linear forest required to partition the edge set E(G). Akiyama, Exoo and Harary conjectured that [Δ/2] ≤ la(G) ≤ [Δ+1/2] 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.
收录类别:EI;SCOPUS;SCIE
资源类型:期刊论文
原文链接:https://www.scopus.com/inward/record.uri?eid=2-s2.0-84899967733&doi=10.1016%2fj.ipl.2014.03.013&partnerID=40&md5=39eb05460f14c67078bf0f9f74ef3267
TOP