树宽较小的图的线性荫度

作者：陈宏宇

来源：山东大学学报(理学版), 2023, 1-5.

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

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

• 单位
  上海应用技术大学