最大度大于等于7的平面图的线性荫度

作者：陈洪玲; 王慧娟^*; 孙凤艳; 薛娟; 高红伟

来源：运筹学学报, 2020, 24(03): 154-160.

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

• 平面图
• 线性森林
• 圈

图的染色问题在组合优化、计算机科学和Hessians矩阵的网络计算等方面具有非常重要的应用。其中图的染色中有一种重要的染色——线性荫度,它是一种非正常的边染色,即在简单无向图中,它的边可以分割成线性森林的最小数量。研究最大度△(G)≥7的平面图G的线性荫度,证明了对于两个固定的整数i,j∈{5,6,7},如果图G中不存在相邻的含弦i,j-圈,则图G的线性荫度为[△/2]。