The adjacent vertex distinguishing total chromatic number
The adjacent vertex distinguishing total chromatic number
复制标题
DOI：
10.1016/j.disc.2012.04.006
复制
发表时间：
2010-09
期刊：
影响因子：
--
通讯作者：
T. Coker;Karen Johannson
中科院分区：
文献类型：
--
作者：
T. Coker;Karen Johannson
一个经过充分研究的概念是总色数。图的正确总着色是顶点和边的着色，使得每对相邻顶点接收不同的颜色，每对相邻边接收不同的颜色，并且每个顶点和入射边接收不同的颜色。本文考虑加强这一条件，并检查总着色所需的最小颜色数，并附加一个属性，即对于任何相邻顶点 u 和 v，关联到 u 的颜色集不同于关联到 v 的颜色集。结果表明，存在一个常数 C，因此对于任何图 G，都存在最多使用 Δ(G)+C 种颜色的着色。
A well-studied concept is that of the total chromatic number. A proper total colouring of a graph is a colouring of both vertices and edges so that every pair of adjacent vertices receive different colours, every pair of adjacent edges receive different colours and every vertex and incident edge receive different colours. This paper considers a strengthening of this condition and examines the minimum number of colours required for a total colouring with the additional property that for any adjacent vertices u and v, the set of colours incident to u is different from the set of colours incident to v. It is shown that there is a constant C so that for any graph G, there exists such a colouring using at most Δ(G)+C colours.