子立方无爪图的单射边色数至多为6

The Injective Chromatic Index of a Claw-Free Subcubic Graph is at Most 6

中文关键词:  单射边染色  单射边色数  无爪图  子立方图

英文关键词:injective edge coloring  injective chromatic index  claw-free  subcubic graph

中文摘要:

      设$G$是一个图. 图$G$的一个单射边染色是指图$G$的一个边染色, 使得距离为$2$的两条边或者在同一个三角形中的两条边染不同的颜色. 图$G$的单射边色数是指图$G$的任意单射边染色所需要的最少颜色数. 关于单射边色数有一个猜想: 任意一个子立方图的单射边色数都不超过$6$. 在本文中, 我们证明了这个猜想对子立方无爪图是成立的, 并且给出图例说明上界$6$是紧的. 同时, 我们的证明隐含了求解这类图不超过$6$种颜色的单射边染色方案的一个线性时间算法.

英文摘要:

      A coloring of edges of a graph $G$ is injective if for any two distinct edges $e_1$ and $e_2$, the coloring of $e_1$ and $e_2$ are distinct if they are at distance $2$ in $G$ or in a common $3$-cycle. The injective chromatic index of $G$ is the minimum number of colors needed for an injective edge coloring of $G$. It was conjectured that the injective chromatic index of any subcubic graph is at most $6$. In this paper, we partially confirm this conjecture by showing that the injective chromatic index of any claw-free subcubic graph is less than or equal to $6$. The bound $6$ is tight and our proof implies a linear-time algorithm for finding an injective edge coloring using at most $6$ colors for such graphs.