一类仙人掌图的星边染色

Star edge-coloring of a class of cactus graphs

摘要: 图 $G$ 的星边染色是指 $G$ 的一个正常边染色，使得 $G$ 中任一长为4的路和长为4的圈均不是2-边染色的. 图 $G$ 的星边色数 $χ'_{s t} (G)$ 表示图 $G$ 有星边染色的最小颜色数. 仙人掌图是一个连通图使得每个块是圈或者边. 利用数学归纳法得到了一类仙人掌图 $C_{n} \cdot C_{m} (n \geq 3, m \geq 3)$ 的星边色数，从而推广已知结果.

Abstract: In the report， a star edge-coloring of a graph $G$ is a proper edge coloring without 2-colored paths or cycles of length 4. The star chromatic index of $G$ ， ${χ^{'}}_{s t} (G)$ ，indicates that $G$ has a star edge-coloring with the smallest number. The cactus graph is a connected graph of which each block is a cycle or an edge. The mathematical induction is performed to obtain a class of cactus graphs $C_{n} \cdot C_{m} (n \geq 3, m \geq 3)$ ， and which are generalized.