一些稀疏图的强边染色

摘要：

图G的强边染色是指对图G进行正常边染色使得任意长度为3的路的三条边染不同的颜色.图G的强边色数,记为x's(G),是使得图G是强k边着色的最小正整数k.2015年,Zang [arXiv:1510.00785]证明了:最大度△(G)=5的图G,x's(G)≤37.本文证明了:最大度△(G)=5且最大平均度小于8/3(或者14/5)的图G,x's(G)≤13(或者14).另外,本文证明了:最大度△(G)≥3的不含K2,3-图子式的图G,x's(G)≤4△(G)-6,这个界是紧的.

关键词：强边染色、稀疏图、不含K2、3-图子式的图

所属期刊栏目：51

分类号：O157.5(代数、数论、组合理论)

在线出版日期：2022-03-01（万方平台首次上网日期，不代表论文的发表时间）

页数：共12页

页码：41-52