树宽较小的图的线性荫度  

Linear arboricity in graphs of low treewidth

作　　者：陈宏宇 CHEN Hongyu(School of Science,Shanghai Institute of Technology,Shanghai 201418,China)

机构地区：[1]上海应用技术大学理学院,上海201418

出　　处：《山东大学学报（理学版）》2024年第6期25-28,35,共5页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金青年科学基金资助项目(11401386);上海应用技术大学中青年科技人才发展基金项目。

摘　　要：设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.

关 键 词：线性荫度 线性染色 树宽 

分 类 号：O157.5[理学—数学]