树宽较小的图的线性荫度
Linear arboricity in graphs of low treewidth
陈宏宇1
作者信息
- 1. 上海应用技木大学理学院,上海 201418
- 折叠
摘要
设G=(V,E)为一个图,如果染相同颜色α的边导出的子图是一个线性森林,其中1≤α≤t,则从E(G)到{ 1,2,…,t}的一个映射φ称为t-线性染色.线性荫度la(G)表示图G的所有t-线性染色中最小的t.本文确定了最大度为Δ,树宽最多为Δ+1/4的图G,其线性荫度la(G)=[Δ/2].
Abstract
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.
关键词
线性荫度/线性染色/树宽Key words
linear arboricity/linear coloring/treewidth引用本文复制引用
基金项目
国家自然科学基金青年科学基金资助项目(11401386)
上海应用技术大学中青年科技人才发展基金项目()
出版年
2024
NETL
NSTL
万方数据