不含5-圈和相邻4-圈的平面图的线性2-荫度的一个上界

作     者：陈宏宇 谭香 CHEN Hongyu;TAN Xiang

作者机构：上海应用技术大学理学院上海201418 山东财经大学数学与数量经济学院济南250014 

出 版 物：《运筹学学报》 (Operations Research Transactions)

年 卷 期：2019年第23卷第1期

页      面：104-110页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：国家自然科学基金青年基金(No.11401386) 

主　　题：平面图 线性2-荫度 圈 

摘      要：图G的一个边分解是指将G分解成子图G_1,G_2,…,G_m使得E(G)=E(G_1)=∪E(G_2)∪…∪E(G_m),且对于i≠j,E(G_i)∩E(G_j)=?.一个线性k-森林是指每个分支都是长度最多为k的路的图.图G的线性k-荫度la_k(G)是使得G可以边分解为m个线性k-森林的最小整数m.显然,la_1(G)是G的边色数χ (G); la_∞(G)表示每条分支路是无限长度时的情况,即通常所说的G的线性荫度la(G).利用权转移的方法研究平面图的线性2-荫度la_2(G).设G是不含有5-圈和相邻4-圈的平面图,证明了若G连通且δ(G)≥2,则G包含一条边xy使得d(x)+d(y)≤8或包含一个2-交错圈.根据这一结果得到其线性2-荫度的上界为[△/2]+4.