论文标题
亚地带图的局部不规则边缘色
Locally irregular edge-coloring of subcubic graphs
论文作者
论文摘要
如果没有两个相邻的顶点具有相同的程度，则图为{\ em局部不规则}。图$ g $的{\ em局部不规则的边缘色}是一个（不适当的）边缘色，以至于任何固定颜色的边缘都会诱导局部不规则的图。在承认本地不规则的边缘色的图表中，即{\ em emodomposable Graphs}，只有一个需要$ 4 $的颜色，而对于所有其他颜色，则认为$ 3 $的颜色足够了。在本文中，我们证明，具有最高度$ 3 $的可分解爪图，所有周期排列图，所有通用的Petersen图都以最多3美元的颜色为本地不规则的边缘色。我们还讨论了$ 2 $的颜色何时足以使本地不规则的边缘颜色的立方图的边缘色，并呈现一个无限的周长$ 4 $的立方图系列，需要$ 3 $。
A graph is {\em locally irregular} if no two adjacent vertices have the same degree. A {\em locally irregular edge-coloring} of a graph $G$ is such an (improper) edge-coloring that the edges of any fixed color induce a locally irregular graph. Among the graphs admitting a locally irregular edge-coloring, i.e., {\em decomposable graphs}, only one is known to require $4$ colors, while for all the others it is believed that $3$ colors suffice. In this paper, we prove that decomposable claw-free graphs with maximum degree $3$, all cycle permutation graphs, and all generalized Petersen graphs admit a locally irregular edge-coloring with at most $3$ colors. We also discuss when $2$ colors suffice for a locally irregular edge-coloring of cubic graphs and present an infinite family of cubic graphs of girth $4$ which require $3$ colors.
