树宽较小的图的线性荫度

摘要

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

关键词

线性荫度 / 线性染色 / 树宽