Adjacent Vertex Distinguishing Edge-Colorings
Adjacent Vertex Distinguishing Edge-Colorings
复制标题
DOI：
10.1137/s0895480102414107
复制
发表时间：
2007-02
期刊：
影响因子：
--
通讯作者：
P. Balister;E. Györi;J. Lehel;R. Schelp
中科院分区：
文献类型：
--
作者：
P. Balister;E. Györi;J. Lehel;R. Schelp
简单图\(G\)的一个邻点可区别边染色是\(G\)的一种正常边染色，使得任意一对相邻顶点所关联的颜色集合都不相同。对于无孤立边的图，研究了使其具有邻点可区别染色所需的最小颜色数\(\chi^\prime_a(G)\)。我们证明了对于最大度\(\Delta(G)=3\)的这类图，\(\chi^\prime_a(G)\leq5\)，并且对于二分图，证明了\(\chi^\prime_a(G)\leq\Delta(G)+2\)。这些界是紧的。对于无孤立边的\(k\) - 色图\(G\)，我们证明了一个较弱的结果，形式为\(\chi^\prime_a(G)=\Delta(G)+O(\log k)\)。
An adjacent vertex distinguishing edge-coloring of a simple graph $G$ is a proper edge-coloring of $G$ such that no pair of adjacent vertices meets the same set of colors. The minimum number of colors $\chi^\prime_a(G)$ required to give $G$ an adjacent vertex distinguishing coloring is studied for graphs with no isolated edge. We prove $\chi^\prime_a(G)\le5$ for such graphs with maximum degree $\Delta(G)=3$ and prove $\chi^\prime_a(G)\le\Delta(G)+2$ for bipartite graphs. These bounds are tight. For $k$-chromatic graphs $G$ without isolated edges we prove a weaker result of the form $\chi^\prime_a(G)=\Delta(G)+O(\log k)$.