圈并三角形图的强边染色

Strong Edge-coloring of Cycle-plus-triangles Graphs

若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.