On Neighbor‐Distinguishing Index of Planar Graphs
On Neighbor‐Distinguishing Index of Planar Graphs
复制标题
DOI：
10.1002/jgt.21764
复制
发表时间：
2014-08
影响因子：
0.9
通讯作者：
M. Horňák;Danjun Huang;Weifan Wang
中科院分区：
文献类型：
--
作者：
M. Horňák;Danjun Huang;Weifan Wang
无孤立边的图G的正常边染色是邻可区别的，如果任意两个相邻顶点有由其关联边的颜色组成的不同集合。G的邻可区别指数是G的邻可区别边染色中的最小颜色数ndi（G）。Zhang，Liu，and Wang在2002年证明了如果G是阶数至少为6的连通图，则ndi（G）≤Δ（G）+2。本文对最大度至少为12的平面图证明了这个猜想。
A proper edge coloring of a graph G without isolated edges is neighbor‐distinguishing if any two adjacent vertices have distinct sets consisting of colors of their incident edges. The neighbor‐distinguishing index of G is the minimum number ndi(G) of colors in a neighbor‐distinguishing edge coloring of G. Zhang, Liu, and Wang in 2002 conjectured that ndi (G)≤Δ(G)+2 if G is a connected graph of order at least 6. In this article, the conjecture is verified for planar graphs with maximum degree at least 12.