Remarks on Vertex-Distinguishing IE-Total Coloring of Complete Bipartite Graphs $K_{4, n}$ and $K_{n, n}$

DOI：10.3770/j.issn:2095-2651.2012.02.003

 作者 单位 陈祥恩 西北师范大学数学与信息科学学院, 甘肃 兰州 730070 辛小青 西北师范大学数学与信息科学学院, 甘肃 兰州 730070 何文玉 西北师范大学数学与信息科学学院, 甘肃 兰州 730070

图 $G$ 的$IE$-全染色是指对 $G$ 的顶点和边进行的染色,使相邻的两个顶点染不同的颜色. 用$C(u)$ 表示在图 $G$的$IE$-全染色$f$ 下点 $u$ 的颜色以及与 $u$关联的所有边的颜色构成的集合. 设$f$是图 $G$ 的一个使用了 $k$种色的$IE$-全染色, 如果对 $G$ 的任二不同顶点 $u$ 与 $v$, 均有$C(u)\neq C(v)$, 那么称 $f$ 为 $G$ 的 $k$-点可区别$IE$-全染色(简记为 $k-VDIET$染色). 使得 $G$ 有 $k-VDIET$染色的最小的正整数$k$ 叫做图 $G$ 的点可区别 $IE$-全色数, 记作$\chi_{vt}^{ie}(G)$. 本文给出了完全二部图 $K_{4, n}$ $(n\geq4)$,$K_{n, n}$ $(5\leq n\leq21)$ 的点可区别$IE$-全色数.

Let $G$ be a simple graph. An IE-total coloring $f$ of $G$ refers to a coloring of the vertices and edges of $G$ so that no two adjacent vertices receive the same color. Let $C(u)$ be the set of colors of vertex $u$ and edges incident to $u$ under $f$. For an IE-total coloring $f$ of $G$ using $k$ colors, if $C(u)\neq C(v)$ for any two different vertices $u$ and $v$ of $V(G)$, then $f$ is called a $k$-vertex-distinguishing IE-total-coloring of $G$, or a $k$-VDIET coloring of $G$ for short. The minimum number of colors required for a VDIET coloring of $G$ is denoted by $\chi_{vt}^{ie}(G)$, and it is called the VDIET chromatic number of $G$. We will give VDIET chromatic numbers for complete bipartite graph $K_{4, n}$ $(n\ge 4)$, $K_{n, n}$ $(5\le n\le 21)$ in this article.