树宽较小的图的线性荫度

Linear arboricity in graphs of low treewidth

设G=(V,E)为一个图,如果染相同颜色α的边导出的子图是一个线性森林,其中1≤α≤t,则从E(G)到{1,2,…,t}的一个映射φ称为t-线性染色。线性荫度la(G)表示图G的所有t-线性染色中最小的t。本文确定了最大度为Δ,树宽最多为Δ+1/4的图G,其线性荫度la(G)=「Δ/2」。

Let G=(V,E)be a graph,a mapφfrom E(G)to{1,2,…,t}is called a t-linear coloring if the induced subgraph of edges having the same colorαis a linear forest for 1≤α≤t.The linear arboricity la(G)is the minimum number t over all t-linear coloring of G.In this paper,we determine la(G)=「Δ/2」for graphs with maximum degreeΔand treewidth at mostΔ+1/4.