6-圈至多含一弦平面图的线性荫度

作者：罗朝阳^*; 孙林

来源：运筹学学报, 2019, 23(02): 113-119.

DOI：10.15960/j.cnki.issn.1007-6093.2019.02.011

• 圈
• 平面图
• 线性荫度
• 权转移方法

线性森林是指每个连通分支都是路的图.图G的线性荫度la(G)等于将其边分解为k个边不交的线性森林的最小整数k.文中利用权转移方法证明了,若G是一个最大度大于等于7且每个6-圈至多含一条弦的平面图,则la(G)=「(△(G))/2」.

• 单位
  昌吉学院