圈并三角形图的强边染色  

Strong Edge-coloring of Cycle-plus-triangles Graphs

作　　者：王侃[1,2] 陆权烽 王维凡 王艺桥 郑丽娜[2] WANG Kan;LU Quanfeng;WANG Weifan;WANG Yiqiao;ZHENG Lina(Xingzhi College,Zhejiang Normal University,Jinhua,Zhejiang,321100,P.R.China;College of Mathematics and Computer Science,Zhejiang Normal University,Jinhua,Zhejiang,321004,P.R.China;School of Management,Beijing University of Chinese Medicine,Beijing,100029,P.R.China)

机构地区：[1]浙江师范大学行知学院,金华浙江321100 [2]浙江师范大学数学与计算机科学学院,金华浙江321004 [3]北京中医药大学管理学院,北京100029

出　　处：《数学进展》2022年第4期647-655,共9页Advances in Mathematics（China）

基　　金：Supported by NSFC (Nos.12031018,12071048,12171436)。

摘　　要：若3n个顶点的图G能够分解成n个点不交的三角形和一个哈密顿圈,则称G为圈并三角形图.图G的强边色数是使得G的边集可划分成k个导出匹配的最小整数k,用χ_(s)’(G)表示.本文证明了每个圈并三角形图G满足χ_(s)’(G)≤19.本文同时猜想19可以改进到18,给出了这一猜想成立的3个充分条件,并构造了一个χ_(s)’(G)=18的圈并三角形图.A graph G is called a cycle-plus-triangles graph if it is the union of n vertexdisjoint triangles and a Hamiltonian cycle on the same vertex set.The strong chromatic indexχ_(s)’(G)of a graph G is the minimum integer k such that the edge set of G can be partitioned into k induced matchings.In this paper,we show that χ_(s)’(G)≤19 for any cycle-plus-triangles graph G.We also conjecture that 19 can be reduced to 18,and give three sufficient conditions such that the conjecture holds.An example of a cycle-plus-triangles graph G with χ_(s)’(G)=18 is constructed.

关 键 词：圈并三角形图 强边染色 强边色数 

分 类 号：O157.5[理学—数学]