平面图的邻点可区别全染色

J4 ›› 2011, Vol. 46 ›› Issue (4): 4-8.

平面图的邻点可区别全染色

李泽鹏¹,王治文², 陈祥恩^1*

1.西北师范大学数学与信息科学学院, 甘肃兰州 730070;
2.宁夏大学数学计算机学院, 宁夏银川 750021

收稿日期:2009-09-28 发布日期:2011-04-21
通讯作者: 陈祥恩(1965- ),男,教授,硕士,硕士研究生导师,研究方向为图的染色理论与图的代数理论. Email: chenxe@nwnu.edu.cn
作者简介:李泽鹏(1987- ),男,硕士,研究方向为图论及其应用. Email: wyzl-lzp@163.com
基金资助:
国家自然科学基金资助项目(10771091); 宁夏大学科学研究基金((E):ndzr10-7)

Adjacent-vertex-distinguishing total coloring of planar bipartite graphs

LI Ze-peng¹, WANG Zhi-wen², CHEN Xiang-en^1*

1. College of Mathematics and Information Science, Northwest Normal University, Lanzhou 730070, Gansu, China;
2. School of Mathematics and Computer Science, Ningxia University, Yinchuan 750021, Ningxia, China

Received:2009-09-28 Published:2011-04-21

摘要/Abstract

摘要：

图G的一个正常全染色f 称为是邻点可区别的, 如果G中任何相邻点的点及其关联边的颜色集合不同。对一个图G进行邻点可区别的正常全染色所用最少颜色数称为G的邻点可区别全色数, 记为χ_at(G)。证明了χ_at(G)≤Δ(G)+2对任意的Δ(G)≥11且围长至少为4的平面图G成立。

关键词: 图; 平面图; 邻点可区别全染色; 邻点可区别全色数

Abstract:

A proper total coloring of G is an adjacent vertex distinguishing total coloring if for any two adjacent vertices, the sets of colors appearing on the vertex and incident edges are different. The smallest number of color of which such a coloring of G exists is called the adjacent vertex distinguishing total chromatic number, and is denoted by χ_at(G). It is proved that χ_at(G)≤Δ(G)+2 for any planar bipartite graph G with maximum degree Δ(G) at least 11 and grith at least 4.

Key words: graphs; planar bipartite graphs; adjacent-vertex-distinguishing total coloring; adjacent-vertex-distinguishing total chromatic number

李泽鹏1,王治文2, 陈祥恩1*. 平面图的邻点可区别全染色[J]. J4, 2011, 46(4): 4-8.

LI Ze-peng1, WANG Zhi-wen2, CHEN Xiang-en1*. Adjacent-vertex-distinguishing total coloring of planar bipartite graphs[J]. J4, 2011, 46(4): 4-8.

参考文献

多维度评价

Viewed

Full text

Abstract

Cited

Shared

Discussed