树宽较小的图的线性荫度

摘要

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

关键词

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

基金资助

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