• 论文 •

若干图的倍图的邻点可区别边(全)染色

1. 西北民族大学数学与计算机科学学院, 甘肃 兰州 730030
• 收稿日期:2014-07-15 修回日期:2015-03-05 出版日期:2015-04-20 发布日期:2015-04-17
• 通讯作者: 田双亮(1965-),男,硕士,教授,研究方向为图论及组合优化.E-mail:sl_tian@163.com E-mail:sl_tian@163.com
• 作者简介:何雪(1988-),女,硕士,研究方向为图论与组合优化.E-mail:hexuebeautiful@163.com
• 基金资助:
西北民族大学研究生科研创新项目(ycx14146);西北民族大学科研创新团队计划资助

Adjacent vertex-distinguishing edge/total colorings of double graph of some graphs

HE Xue, TIAN Shuang-liang

1. School of Mathematics and Computer Science, Northwest University for Nationalities, Lanzhou 730030, Gansu, China
• Received:2014-07-15 Revised:2015-03-05 Online:2015-04-20 Published:2015-04-17

Abstract: Let G be a simple graph with vertex set V(G) and edge set E(G). An edge-coloring σ of G is called an adjacent vertex distinguishing edge-coloring of G if Cσ(u)≠Cσ(v) for any uv∈E(G), where Cσ(u) denotes the set of colors of edges incident with u. A total-coloring σ of G is called an adjacent vertex distinguishing total-coloring of G if Sσ(u)≠Sσ(v) for any uvE(G), where Sσ(u) denotes the set of colors of edges incident with u together with the color assigned to u. The minimum number of colors required for an adjacent vertex-distinguishing edge-coloring (resp. total-coloring) of G is called adjacent vertex-distinguishing edge (resp. total) chromatic number, and denoted by χ'as(G) (resp. χat(G)). The upper bounds for these parameters of the double graph D(G) of graph G are given in this paper. Specifically, the exact value of these parameters for the double graph of complete graphs and trees are determined.

• O157.5