论文标题
恒星边缘彩色
Star Edge-Coloring of Square Grids
论文作者
论文摘要
图$ g $的星形颜色是一种适当的边缘色，没有双重路径或长度为4的周期。最小的整数$ k $，因此$ g $承认带有$ k $颜色的星形颜色是$ g $的星形索引。在有关该主题的开创性论文中，dvo夏克，莫哈尔（Mohar）和Šámal询问了完整图的星形索引在顶点的数量中是线性的，并且给出了几乎线性的上限。他们的问题仍然是开放的，因此，为了更好地理解星形索引的行为，该参数已在许多其他类别的图表中进行了研究。在本文中，我们考虑了正方形网格的恒星边缘色；也就是说，路径和周期的笛卡尔产物以及两个循环的笛卡尔产物。我们提高了以前建立的界限，作为主要贡献，我们证明了两个类别的星形色索引均为$ 6 $或$ 7 $，除了Prisms。此外，我们为许多考虑的图提供了许多精确值。
A star edge-coloring of a graph $G$ is a proper edge-coloring without bichromatic paths or cycles of length four. The smallest integer $k$ such that $G$ admits a star edge-coloring with $k$ colors is the star chromatic index of $G$. In the seminal paper on the topic, Dvořák, Mohar, and Šámal asked if the star chromatic index of complete graphs is linear in the number of vertices and gave an almost linear upper bound. Their question remains open, and consequently, to better understand the behavior of the star chromatic index, this parameter has been studied for a number of other classes of graphs. In this paper, we consider star edge-colorings of square grids; namely, the Cartesian products of paths and cycles and the Cartesian products of two cycles. We improve previously established bounds and, as a main contribution, we prove that the star chromatic index of graphs in both classes is either $6$ or $7$ except for prisms. Additionally, we give a number of exact values for many considered graphs.
