西北师范大学，数学与统计学院，甘肃 兰州

收稿日期：2022年3月10日；录用日期：2022年4月14日；发布日期：2022年4月21日

摘要

图G的一个E-全染色f是指让相邻两个顶点之间染不同的颜色，并且让每条关联边与它的端点染不同颜色的全染色。如果对图G中任意两个不同的顶点u和v，点u和点v的色集合不相同，则称f为图G的VDET染色，即图G的点可区别E-全染色。在本篇论文中我们利用反证法以及分析法，讨论完全二部图 $K_{11,n}\left(89\le n\le 212\right)$ 的VDET染色问题，并利用构造染色法给出 $K_{11,n}\left(89\le n\le 212\right)$ 的最优VDET染色的染色方案。

关键词

完全二部图，E-全染色，VDET染色，VDET染色数

Vertex-Distinguishing E-Total Coloring of Complete Bipartite Graph $K_{11,n}\left(89\le n\le 212\right)$

Dawei Han

College of Mathematics and Statistics, Northwest Normal University, Lanzhou Gansu

Received: Mar. 10^th, 2022; accepted: Apr. 14^th, 2022; published: Apr. 21^st, 2022

ABSTRACT

Let G be a simple graph. The total coloring f of G is called an E-total coloring if two adjacent vertices have different colors, and dot each associated edge a different color from its end. For an VDET coloring f of graph G, if $C\left(u\right)\ne C\left(v\right)$ for any two distinct vertices u and v of V(G), then f is called VDET; we shall abbreviate the vertex-distinguishing E-total coloring of G. This paper uses the contradiction and analysis method. We discussed the VDET coloring problem of complete bipartite graph $K_{11,n}\left(89\le n\le 212\right)$. The structure staining method was used to give the best staining scheme of optimal VDET coloring of complete bipartite graph $K_{11,n}\left(89\le n\le 212\right)$.

Keywords:Complete Bipartite Graph, E-Total Coloring, VDET Coloring, VDET Coloring Number

Copyright © 2022 by author(s) and Hans Publishers Inc.

This work is licensed under the Creative Commons Attribution International License (CC BY 4.0).

http://creativecommons.org/licenses/by/4.0/

1. 引言

在图论研究中，图的染色问题非常有趣且具有极其重要的研究意义和应用价值，近年来，随着图的染色问题在现实生活中的广泛应用，它逐渐成为被许多学者研究的重要领域之一，点可区别的正常边染色或一般边染色、点可区别的正常全染色或一般全染色以及点可区别的未必正常全染色等一系列问题到现在依然是图论研究者追求且有趣的难题。

设图G是一个简单图。图G的一个一般全染色是指用不同的颜色对图G的所有顶点和G的边进行染色。设图G的一个全染色f (正常或未必正常)和图G的任意一个顶点X，用C(X)表示顶点X的色集合，它是指顶点X所染颜色及与这个顶点关联边所染颜色组成的集合。在这篇文章中讨论的是图的点可区别的一类未必正常全染色。如果让相邻两个顶点之间染不同的颜色，并且让每条关联边与它的端点染不同颜色则称为图G的一个E-全染色。设f为G的一个E-全染色，若满足对 $\forall u,v\in V\left(G\right)$ ， $u\ne v$ ，有 $C\left(u\right)\ne C\left(v\right)$ ，则称f为G的VDET染色，也就是点可区别E-全染色。图G的VDET色数 ${\chi }_{vt}^e\left(G\right)=\min \left\{k|G存在k\text{-VDET}染色\right\}$。

文献 [1] [2] 主要提出了图的点可区别等概念，文献 [3] [4] [5] [6] 陈祥恩等人讨论了完全二部图 $K_{2,n}$ 、星、扇、轮、路和圈的点可区别E-全染色；文献 [7] [8] 讨论了完全二部图 $K_{10,n}$ 的点可区别E-全染色。 [9] [10] [11] [12] 中讨论了完全二部图 $K_{2,n}$ ， $K_{3,n}$ ， $K_{6,n}$ ， $K_{7,n}$ 的点可区别E-全染色，文献 [13] 杨芳等人讨论了完全图和合成图的点可区别正常边染色，文献 [14] [15] 中得出了 $m{C}_4$ 和 $m{C}_3$ 的一般点可区别全染色。本文主要通过讨论 $K_{11,n}\left(89\le n\le 212\right)$ 的VDET染色并且得到 $K_{11,n}$ 的VDET色数。

令 $V\left(K_{11,n}\right)=X\cup Y$ ， $E\left(K_{11,n}\right)=\left\{u_i{v}_j:1\le i\le 11,1\le j\le n\right\}$ ，其中， $X=\left\{u_1,u_2,\cdots ,u_{11}\right\}$ ， $Y=\left\{V_1,V_2,\cdots ,V_{\mathrm{n}}\right\}$。设 $C\left(X\right)=\left\{C\left(u_1\right),C\left(u_2\right),\cdots ,C\left(u_{11}\right)\right\}$ ， $C\left(Y\right)=\left\{C\left(v_1\right),C\left(v_2\right),\cdots ,C\left(v_j\right)\right\}$。

2. 引理

引理1 当 $11\le n\le 28$ 时，有 ${\chi }_{vt}^e\left(K_{11,n}\right)=6$。

引理2 当 $29\le n\le 88$ 时，有 ${\chi }_{vt}^e\left(K_{11,n}\right)=7$。

3. 主要结果及证明

定理1 当 $89\le n\le 212$ 时，有 ${\chi }_{vt}^e\left(K_{11,n}\right)=8$。

证明：用反证法。首先，假设 $K_{11,n}$ 存在7-VDET染色，利用分析法可以推出矛盾，然后利用构造染色法给出 $K_{11,n}$ 的一个8-VDET染色。

假设 $K_{11,n}$ 存在一个7-VDET染色f，用颜色1, 2, 3, 4, 5, 6, 7去染色，则我们只需要考虑以下六种情形。

情形1： $u_1,u_2,\cdots ,u_{11}$ 的11个顶点中颜色互不相同的仅有一种。不妨设 $f\left(u_i\right)=1\left(i=1,2,\cdots ,11\right)$ ，那么每个 $C\left(v_j\right)$ 都不能用1去染色。因此{1, 2, 3, 4, 5, 6, 7}中可作为C(Y)的子集数目为

$\left(\begin{array}{c}7-1\\ 2\end{array}\right)+\left(\begin{array}{c}7-1\\ 3\end{array}\right)+\left(\begin{array}{c}7-1\\ 4\end{array}\right)+\left(\begin{array}{c}7-1\\ 5\end{array}\right)+\left(\begin{array}{c}7-1\\ 6\end{array}\right)=57$。57个集合不能够区别出Y中的n个顶点，矛盾。

情形2： $u_1,u_2,\cdots ,u_{11}$ 的11个顶点中颜色互不相同的仅有两种。不妨设 $f\left(u_i\right)=\left\{1,2\right\}\left(i=1,2,\cdots ,11\right)$ ，则每个 $C\left(v_j\right)$ 是2-子集时不能用颜色1或2去染色。因此 $\left\{1,2,3,4,5,6,7\right\}$ 中可作为C(Y)的子集数目为

$\left(\begin{array}{c}7\\ 2\end{array}\right)+\left(\begin{array}{c}7\\ 3\end{array}\right)+\left(\begin{array}{c}7\\ 4\end{array}\right)+\left(\begin{array}{c}7\\ 5\end{array}\right)+\left(\begin{array}{c}7\\ 6\end{array}\right)+\left(\begin{array}{c}7\\ 7\end{array}\right)-11=109$。其中，当 $110\le n\le 212$ 时，109个集合不能够区别开Y中的n

个顶点，矛盾。下面我们只需考虑当 $89\le n\le 109$ 时的情形。令 $\mathfrak{B}={\mathfrak{B}}_1\cup {\mathfrak{B}}_2\cup {\mathfrak{B}}_3$ ，其中：

${\mathfrak{B}}_1=\left\{\left\{\text{3},\text{4}\right\},\left\{\text{3},\text{5}\right\},\left\{\text{3},\text{6}\right\},\left\{\text{3},\text{7}\right\},\left\{\text{4},\text{5}\right\},\left\{\text{4},\text{6}\right\},\left\{\text{4},\text{7}\right\},\left\{\text{5},\text{6}\right\},\left\{\text{5},\text{7}\right\},\left\{\text{6},\text{7}\right\}\right\}$ ；

${\mathfrak{B}}_2=\left\{\left\{1,2,3\right\},\left\{1,2,4\right\},\left\{1,2,5\right\},\left\{1,2,6\right\},\left\{1,2,7\right\}\right\}$ ；

${\mathfrak{B}}_3$ 为{1, 2, 3, 4, 5, 6, 7}的所有4、5、6、7-子集和除去 ${\mathfrak{B}}_2$ 中的3-子集所构成的集合，共94个集合。

观察到在 $\mathfrak{B}$ 中包含i的集合有57个 $\left(i=1,2\right)$。在 $\mathfrak{B}$ 中包含j的集合有61个 $\left(j=3,4,5,6,7\right)$。因此，每个 $C\left(u_i\right)$ 至少包含3种颜色，故 $C\left(X\right)\subseteq {\mathfrak{B}}_2\cup {\mathfrak{B}}_3$ ， $C\left(X\right)\cup C\left(Y\right)\subseteq \mathfrak{B}$ ，有 $11+n\le 109$ ，可得 $n\le 98$。所以当 $99\le n\le 212$ 时， $\mathfrak{B}$ 中的集合不能够区别出X和Y中的 $\left(11+n\right)$ 个顶点，矛盾。以下就只需要考虑当 $89\le n\le 98$ 时的情形。

情形2.1： ${\mathfrak{B}}_2\cap C\left(Y\right)\ne \varnothing$ ，则 $1,2\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$

情形2.1.1： ${\mathfrak{B}}_1\cap C\left(Y\right)\ne \varnothing$ ，(否则，若 ${\mathfrak{B}}_1\cap C\left(Y\right)=\varnothing$ ，则 $11+n\le 109-10$,$n\le 88$ ，矛盾。)，则每个 $C\left(u_i\right)$ 恰好同时包含3, 4, 5, 6, 7中的任意1种色，不妨设 $3\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ 则 $\left\{4,5\right\},\left\{4,6\right\},\left\{4,7\right\},\left\{5,6\right\},\left\{5,7\right\},\left\{6,7\right\}\notin C\left(Y\right)$ ，从而 $11+n\le 109-6$ ，可得 $n\le 92$ ，当 $93\le n\le 98$ 时，92个集合不能够区别出Y中的n个顶点，矛盾。下面仅考虑 $89\le n\le 92$ 时的情形。此时{1, 4, 5}, {1, 4, 6}, {1, 4, 7}, {1, 5, 6}, {1, 5, 7}, {1, 6, 7}中至多有3集合不属于C(Y)，因此每个顶点为1的色集合至少同时包含4, 5, 6, 7中的任意两种色，不妨设 $4,5\in C\left(u_i\right)$ ， $f\left(u_i\right)=1$ ， $\left(i=1,2,\cdots ,11\right)$ ；同理{2, 4, 5}, {2, 4, 6}, {2, 4, 7}, {2, 5, 6}, {2, 5, 7}, {2, 6, 7}中至多有3个集合不属于C(Y)，因此每个顶点为2的色集合至少同时包含4, 5, 6, 7中的任意两种色，不妨设 $f\left(u_i\right)=2$ 时， $a,b\in C\left(u_i\right),\left(i=1,2,\cdots ,11\right)$ ，其中 $4\le a<b\le 7$ ，此时 $\left\{4,5\right\}\cap \left\{a,b\right\}=\varnothing$ 即 $\left\{a,b\right\}=\left\{6,7\right\}$。从而每个 $C\left(u_i\right)$ 只能是下面集合中的某一个：{1, 2, 3, 4, 5}, {1, 2, 3, 6, 7}, {1, 2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 7}, {1, 2, 3, 4, 6, 7}, {1, 2, 3, 5, 6, 7}, {1, 2, 3, 4, 5, 6, 7}，7个集合不能够区别开X中的11个顶点，矛盾。

情形2.1.2：如果 ${\mathfrak{B}}_2\cap C\left(X\right)=\varnothing$ ，则 $C\left(Y\right)\subseteq {\mathfrak{B}}_2$ ，那么每个 $C\left(u_i\right)$ 要至少同时包含3, 4, 5, 6, 7中的任意2种色，不妨设 $3,4\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，从而每个 $C\left(u_i\right)$ 只能是下面的集合中的任意一个：{1, 2, 3, 4}, {1, 2, 3, 4, 5}, {1, 2, 3, 4, 6}, {1, 2, 3, 4, 7}, {1, 2, 3, 4, 5, 6}, {1, 2, 3, 4, 5, 7}, {1, 2, 3, 4, 6, 7}, {1, 2, 3, 4, 5, 6, 7}，矛盾。

情形2.2： ${\mathfrak{B}}_2\cap C\left(Y\right)=\varnothing$。

情形2.2.1： ${\mathfrak{B}}_2\cap C(X)\ne \varnothing$ ，则3, 4, 5, 6, 7的颜色中至少有一种颜色同时包含在每个 $C\left(u_i\right)$ 中，不妨设 $3\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，则 $C\left(Y\right)⊈\left\{\left\{4,5\right\},\left\{4,6\right\},\left\{4,7\right\},\left\{5,6\right\},\left\{5,7\right\},\left\{6,7\right\},\left\{1,4,5\right\},\left\{1,4,6\right\},\left\{1,4,7\right\},\left\{1,5,6\right\},\left\{1,5,7\right\},\left\{1,6,7\right\}\right\}$ ， 则有 $n\le 109-16-10$ ， $n\le 83$ ，矛盾。

情形2.2.2： ${\mathfrak{B}}_2\cap C\left(X\right)=\varnothing$ 此时， $C\left(X\right)\cup C\left(Y\right)\subseteq {\mathfrak{B}}_2\cup {\mathfrak{B}}_3$ ，有 $11+n\le 10+94$ ，即 $n\le 93$ ，因此当 $94\le n\le 98$ 时，矛盾。以下仅考虑 $89\le n\le 93$ 时的情形，此时 ${\mathfrak{B}}_1$ 中至少有6个集合属于C(Y)。

1) ${\mathfrak{B}}_1$ 中恰有6个或7个元素属于C(Y)，这时3, 4, 5, 6, 7中至少有两种色会同时包含在每个 $C\left(u_i\right)$ 中，不妨设 $3,4\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，则 $C\left(Y\right)⊈\left\{\left\{\text{5},\text{6}\right\},\left\{\text{5},\text{7}\right\},\left\{\text{6},\text{7}\right\}\right\}$ ，即 $11+n\le 109-5-3$ ， $n\le 90$ ，因此当 $91\le n\le 98$ 时，矛盾。以下仅考虑 $89\le n\le 90$ 时的情形。 $C\left(X\right)⊈\left\{\left\{\text{1},\text{5},\text{6}\right\},\left\{\text{1},\text{5},\text{7}\right\},\left\{\text{1},\text{6},\text{7}\right\},\left\{\text{2},\text{5},\text{6}\right\},\left\{\text{2},\text{5},\text{7}\right\},\left\{\text{2},\text{6},\text{7}\right\}\right\}$ ，且至多有一个不是C(Y)的集合， $C\left(Y\right)\subseteq \left\{\left\{1,5,6\right\},\left\{1,5,7\right\},\left\{1,6,7\right\}\right\}$ ，则X中顶点为1的色集合中就至少会包含5, 6, 7中的任意两种颜色，不妨设 $f\left(u_i\right)=1$ ， $5,6\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，由 $C\left(Y\right)\subseteq \left\{\left\{2,5,6\right\},\left\{2,5,7\right\},\left\{2,6,7\right\}\right\}$ ，可得颜色为2的C(X)包含5, 6, 7中的最少两种相同的颜色，设对每个满足 $f\left(u_j\right)=2$ 的 $u_j$ 都有 $a,b\in C\left(u_j\right)$ ， $5\le a<b\le 7$。由 $\left\{4,5\right\}\cap \left\{a,b\right\}\ne \varnothing$ ，则 $C\left(u_i\right)$ 至少同时包含5, 6中的任意一种色，不妨设 $5\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ 因此， $C\left(X\right)\subseteq \left\{\left\{1,3,4,5,6\right\},\left\{1,3,4,5,6,7\right\},\left\{2,3,4,5,6\right\},\left\{2,3,4,5,6,7\right\},\left\{1,2,3,4,5,6\right\},\left\{1,2,3,4,5,6,7\right\}\right\}$ ，矛盾。

2) ${\mathfrak{B}}_1$ 中恰有8个或9个元素属于C(Y)，这时 $C\left(u_i\right)$ 中同时包含3, 4, 5, 6, 7至少有3种相同的色，不妨设 $3,4,5\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，则 $\left\{6,7\right\}\notin C\left(Y\right)$ ，即 $11+n\le 109-5-1$ ，即 $n\le 92$ ，因此当 $93\le n\le 98$ 时，矛盾。以下仅考虑 $89\le n\le 92$ 时的情形。 $C\left(X\right)⊈\left\{\left\{1,6,7\right\},\left\{2,6,7\right\},\left\{1,2,6,7\right\}\right\}$ 且至少有1个属于C(Y)，不妨设Y中某个顶点 $v_{j0}$ 的色集合 $C\left(v_{j0}\right)=\left\{1,2,6,7\right\}$ ， $f\left(v_{j0}\right)=7$ ，则每个 $C\left(u_i\right)$ 包含{1, 2}, {1, 6}或{2, 6}

( $i=1,2,\cdots ,11$ )，此， $\begin{array}{l}C\left(X\right)\subseteq \{\left\{\text{1},\text{2},\text{3},\text{4},\text{5}\right\},\left\{\text{1},\text{2},\text{3},\text{4},\text{5},\text{6}\right\},\left\{\text{1},\text{2},\text{3},\text{4},\text{5},\text{7}\right\},\left\{\text{1},\text{2},\text{3},\text{4},\text{5},\text{6},\text{7}\right\},\\ \left\{\text{1},\text{3},\text{4},\text{5},\text{6}\right\},\left\{\text{1},\text{3},\text{4},\text{5},\text{6},\text{7}\right\},\left\{\text{2},\text{3},\text{4},\text{5},\text{6}\right\},\left\{\text{2},\text{3},\text{4},\text{5},\text{6},\text{7}\right\}\}\end{array}$ ，矛盾。

3) $C\left(Y\right)\subseteq {\mathfrak{B}}_1$ ，这时 $C\left(u_i\right)$ 中至少同时包含3, 4, 5, 6, 7中的任意4种色，不妨设 $3,4,5,6\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，从而满足 $C\left(X\right)\subseteq \left\{\left\{1,3,4,5,6\right\},\left\{2,3,4,5,6\right\},\left\{1,3,4,5,6,7\right\},\left\{2,3,4,5,6,7\right\},\left\{1,2,3,4,5,6\right\},\left\{1,2,3,4,5,6,7\right\}\right\}$ ，矛盾。

情形3： $u_1,u_2,\cdots ,u_{11}$ 的11个顶点中颜色互不相同的仅有三种。不妨设 $f\left(u_i\right)=\left\{1,2,3\right\}\left(i=1,2,\cdots ,11\right)$ ，则当 $C\left(v_j\right)$ 是2-子集时，不能用颜色1, 2或3染色，且每个 $C\left(v_j\right)$ 都不是{1, 2, 3}。因此{1, 2, 3, 4, 5, 6, 7}

可作为C(Y)的子集数目为 $\left(\begin{array}{c}7\\ 2\end{array}\right)+\left(\begin{array}{c}7\\ 3\end{array}\right)+\left(\begin{array}{c}7\\ 4\end{array}\right)+\left(\begin{array}{c}7\\ 5\end{array}\right)+\left(\begin{array}{c}7\\ 6\end{array}\right)+\left(\begin{array}{c}7\\ 7\end{array}\right)-16=104$。当 $105\le n\le 212$ 时，104个集合不

能够区分出Y中的n个顶点，矛盾。下面仅考虑当 $89\le n\le 104$ 时的情形。令 $ℭ={ℭ}_1\cup {ℭ}_2\cup {ℭ}_3$ ，其中：

${ℭ}_1=\left\{\left\{4,5\right\},\left\{4,6\right\},\left\{4,7\right\},\left\{5,6\right\},\left\{5,7\right\},\left\{6,7\right\}\right\}$ ；

${ℭ}_2=\left\{\left\{\text{1},\text{2},\text{4}\right\},\left\{\text{1},\text{2},\text{5}\right\},\left\{\text{1},\text{2},\text{6}\right\},\left\{\text{1},\text{2},\text{7}\right\},\left\{\text{1},\text{3},\text{4}\right\},\left\{\text{1},\text{3},\text{5}\right\},\left\{\text{1},\text{3},\text{6}\right\},\left\{\text{1},\text{3},\text{7}\right\},\left\{\text{2},\text{3},\text{4}\right\},\left\{\text{2},\text{3},\text{5}\right\},\left\{\text{2},\text{3},\text{6}\right\},\left\{\text{2},\text{3},\text{7}\right\}\right\}$ ；

${ℭ}_3$ 是{1, 2, 3, 4, 5, 6, 7}的子集中的4-、5-、6-、7-子集和不在 ${ℭ}_2\cup \left\{\left\{1,2,3\right\}\right\}$ 中的3-子集，共有86个。

观察到 $ℭ$ 中包含57个i集合 $\left(i=1,2,3\right)$ ，包含60个j集合 $\left(j=4,5,6,7\right)$ ，因此每个 $C\left(u_i\right)$ 至少包含任意3种色，故 $C\left(X\right)\subseteq {ℭ}_2\cup {ℭ}_3$ ，则 $C\left(X\right)\cup C\left(Y\right)\subseteq \left\{\left\{1,2,3\right\}\right\}\cup ℭ$ ，有 $11+n\le 1+104$ ，可得 $n\le 94$ ，从而当 $95\le n\le 212$ 时，105个集合不能够区别开X和Y中的 $\left(11+n\right)$ 个顶点，矛盾。下面仅考虑 $89\le n\le 104$ 时的情形。此时在 ${ℭ}_1$ 中至少有1个集合属于C(Y)，因此每个 $C\left(u_i\right)$ 中至少包含4, 5, 6, 7中的任意1种色，故 $\left\{1,2,3\right\}\notin C\left(X\right)$ ， $C\left(X\right)\cup C\left(Y\right)\subseteq ℭ$ ，有 $11+n\le 104$ ， $n\le 93$。以下仅考虑 $89\le n\le 93$ 时的情形。此时 $ℭ$ 中至多有四个集合不属于C(X)和C(Y)。

情形3.1： ${ℭ}_1$ 中恰有3个集合是属于C(X)和C(Y)的，则每个 $C\left(u_i\right)$ 刚好包含4, 5, 6, 7中的任意一种色，不妨设 $4\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ 则 $C\left(Y\right)⊈\left\{\left\{\text{5},\text{6}\right\},\left\{\text{5},\text{7}\right\},\left\{\text{6},\text{7}\right\}\right\}$ ，

$C\left(X\right)⊈\left\{\left\{1,2,5\right\},\left\{1,2,6\right\},\left\{1,2,7\right\},\left\{1,3,5\right\},\left\{1,3,6\right\},\left\{1,3,7\right\},\left\{2,3,5\right\},\left\{2,3,6\right\},\left\{2,3,7\right\}\right\}$ ，且至多有2个不属于

C(Y)，因此， $1,2,3\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，从而 $\begin{array}{l}C\left(X\right)\subseteq \{\left\{1,2,3,4\right\},\left\{1,2,3,4,5\right\},\left\{1,2,3,4,5,6\right\},\left\{1,2,3,4,5,6,7\right\},\\ \left\{1,2,3,4,6\right\},\left\{1,2,3,4,7\right\},\left\{1,2,3,4,5,7\right\},\left\{1,2,3,4,6,7\right\}\}\end{array}$ ，矛盾。

情形3.2： ${ℭ}_1$ 中的集合恰有4个或5个属于C(X)和C(Y)，则每个 $C\left(u_i\right)$ 恰好包含4, 5, 6, 7中的任意两种色，不妨设 $4,5\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，则 $\left\{6,7\right\}\notin C\left(Y\right)$ ， ${ℭ}_2\notin C\left(Y\right)$ ，因此有 $1,2,3\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，从而 $C\left(X\right)\subseteq \left\{\left\{1,2,3,4,5\right\},\left\{1,2,3,4,5,6\right\},\left\{1,2,3,4,5,7\right\},\left\{1,2,3,4,5,6,7\right\}\right\}$ ，矛盾。

情形3.3： ${ℭ}_1\cap C\left(X\right)\ne \varnothing$ 且 ${ℭ}_1\cap C\left(Y\right)\ne \varnothing$ ，则每个 $C\left(u_i\right)$ 恰好包含4,5,6,7中的任意3种颜色，不妨设 $4,5,6\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，则 $C\left(X\right)⊈{ℭ}_2$ 且 ${ℭ}_2$ 中至多有四个集合不属于C(Y)，因此 $1,2,3\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$ ，从而 $C\left(X\right)\subseteq \left\{\left\{1,2,3,4,5,6\right\},\left\{1,2,3,4,5,6,7\right\}\right\}$ ，矛盾。

情形3.4： ${ℭ}_1\cap C\left(X\right)=\varnothing$ 且 ${ℭ}_1\cap C\left(Y\right)=\varnothing$ ，则 $C\left(X\right)\cup C\left(Y\right)\subseteq {ℭ}_2\cup {ℭ}_3$ ，则 $11+n\le 86+12$ ， $n\le 87$ ，矛盾。

情形4： $u_1,u_2,\cdots ,u_{11}$ 的11个顶点颜色中互不相同的仅有四种。设 $f\left(u_i\right)=\left\{1,2,3,4\right\}\left(i=1,2,\cdots ,11\right)$ ，则当 $C\left(v_j\right)$ 是2-子集时，不包含颜色1, 2, 3或4， $C\left(Y\right)⊈\left\{\left\{\text{1},\text{2},\text{3}\right\},\left\{\text{1},\text{2},\text{4}\right\},\left\{\text{1},\text{3},\text{4}\right\},\left\{\text{2},\text{3},\text{4}\right\},\left\{\text{1},\text{2},\text{3},\text{4}\right\}\right\}$ ，因此{1,

2, 3, 4, 5, 6, 7}可作为C(Y)的成员数目为 $\left(\begin{array}{c}7\\ 2\end{array}\right)+\left(\begin{array}{c}7\\ 3\end{array}\right)+\left(\begin{array}{c}7\\ 4\end{array}\right)+\left(\begin{array}{c}7\\ 5\end{array}\right)+\left(\begin{array}{c}7\\ 6\end{array}\right)+\left(\begin{array}{c}7\\ 7\end{array}\right)-18-5=97$。当 $98\le n\le 212$ 时，

97个集合不能区分Y中的n个顶点，矛盾。下面仅考虑 $89\le n\le 97$ 时的情形。令 $\mathfrak{D}={\mathfrak{D}}_1\cup {\mathfrak{D}}_2\cup {\mathfrak{D}}_3$ ，其中：

${\mathfrak{D}}_1=\left\{\left\{5,6\right\},\left\{5,7\right\},\left\{6,7\right\}\right\}$ ； $\begin{array}{l}{\mathfrak{D}}_2=\{\left\{\text{1},\text{2},\text{5}\right\},\left\{\text{1},\text{2},\text{6}\right\},\left\{\text{1},\text{2},\text{7}\right\},\left\{\text{1},\text{3},\text{5}\right\},\left\{\text{1},\text{3},\text{6}\right\},\left\{\text{1},\text{3},\text{7}\right\},\left\{\text{1},\text{4},\text{5}\right\},\left\{\text{1},\text{4},\text{6}\right\},\left\{\text{1},\text{4},\text{7}\right\},\\ \left\{\text{2},\text{3},\text{5}\right\},\left\{\text{2},\text{3},\text{6}\right\},\left\{\text{2},\text{3},\text{7}\right\},\left\{\text{3},\text{4},\text{5}\right\},\left\{\text{3},\text{4},\text{6}\right\},\left\{\text{3},\text{4},\text{7}\right\},\left\{\text{2},\text{4},\text{5}\right\},\left\{\text{2},\text{4},\text{6}\right\},\left\{\text{2},\text{4},\text{7}\right\}\}\end{array}$ ；

${\mathfrak{D}}_3$ 是{1, 2, 3, 4, 5, 6, 7}中的5-、6-、7-子集以及除去{1, 2, 3, 4}的4-子集及不在 ${\mathfrak{D}}_2\cup \left\{\left\{1,2,3\right\},\left\{1,2,4\right\},\left\{1,3,4\right\},\left\{2,3,4\right\}\right\}$ 中的3-子集共76个。

观察到 $\mathfrak{D}$ 中包含57个i集合( $i=1,2,3,4$ )，包含60个j集合( $j=5,6,7$ ), 因此每个至少包含三种色， $C\left(X\right)\cup C\left(Y\right)\subseteq D\cup \left\{\left\{\text{1},\text{2},\text{3}\right\},\left\{\text{1},\text{2},\text{4}\right\},\left\{\text{1},\text{3},\text{4}\right\},\left\{\text{2},\text{3},\text{4}\right\},\left\{\text{1},\text{2},\text{3},\text{4}\right\}\right\}$ ，有 $11+n\le 97+5$ ，即 $n\le 91$。从而当 $92\le n\le 212$ 时，102个集合不能够区别开X和Y中的 $\left(11+n\right)$ 个顶点，矛盾。所以以下仅考虑当 $89\le n\le 91$ 时的情形，则 ${\mathfrak{D}}_1$ 中至多有3个集合不属于C(Y)。

情形4.1： ${\mathfrak{D}}_1$ 中至少有1个集合是属于C(Y)的，则在5, 6, 7中至少有1种色同时包含在每个 $C\left(u_i\right)$ 中，不妨设 $5\in C\left(u_i\right)\left(i=1,2,\cdots ,11\right)$。因此{1, 2, 3}, {1, 2, 4}, {1, 3, 4}, {2, 3, 4}, {1, 2, 3, 4}均不属于C(X)，故 $C\left(X\right)\cup C\left(Y\right)\subseteq \mathfrak{D}$ ，即 $11+n\le 97$ ， $n\le 86$ ，86个集合不能够区别出Y中的n个顶点，矛盾。

情形4.2： $C\left(Y\right)⊈{\mathfrak{D}}_1$ ，则 $C\left(X\right)\subseteq \left\{\left\{1,2,3\right\},\left\{1,2,4\right\},\left\{1,3,4\right\},\left\{2,3,4\right\},\left\{1,2,3,4\right\}\right\}$ ，不妨设 $C\left(u_{i0}\right)=\left\{1,2,3\right\}$ ， $f\left(u_{i0}\right)=1$ ，则每个 $C\left(v_j\right)$ 包含颜色2或3，故

$\begin{array}{l}C\left(Y\right)⊈\{\left\{\text{1},\text{4},\text{5}\right\},\left\{\text{1},\text{4},\text{6}\right\},\left\{\text{1},\text{4},\text{7}\right\},\left\{\text{1},\text{5},\text{6}\right\},\left\{\text{1},\text{5},\text{7}\right\},\left\{\text{4},\text{5},\text{6}\right\},\left\{\text{4},\text{5},\text{7}\right\},\left\{\text{5},\text{6},\text{7}\right\},\\ \left\{\text{4},\text{5},\text{6},\text{7}\right\},\left\{\text{1},\text{4},\text{5},\text{6}\right\},\left\{\text{1},\text{4},\text{5},\text{7}\right\},\left\{\text{1},\text{5},\text{6},\text{7}\right\},\left\{\text{1},\text{4},\text{5},\text{6},\text{7}\right\}\}\end{array}$ ，

故 $C\left(Y\right)\subseteq {\mathfrak{D}}_2\cup {\mathfrak{D}}_3\backslash \left\{1,4,5\right\},\left\{1,6,7\right\},\left\{4,5,6,7\right\},\left\{1,4,5,6\right\},\left\{1,4,5,7\right\},\left\{1,5,6,7\right\},\left\{1,4,5,6,7\right\}$ 有 $n\le 15+79-13$ ，得 $n\le 81$ ，81个集合不能够区别开Y中的n个顶点，矛盾。

情形5： $u_1,u_2,\cdots ,u_{11}$ 的11个顶点颜色中互不相同的仅有五种。不妨设 $f\left(u_i\right)=\left\{1,2,3,4,5\right\}\left(i=1,2,\cdots ,11\right)$ ，当 $C\left(v_j\right)$ 是2-子集时，不包含1, 2, 3, 4或5且每个 $C\left(v_j\right)$ 也都不是{1, 2, 3, 4, 5}的3-子集、4-子集、5-子集，

共有 $\left(\begin{array}{c}5\\ 3\end{array}\right)+\left(\begin{array}{c}5\\ 4\end{array}\right)+\left(\begin{array}{c}5\\ 5\end{array}\right)=16$ 个，因此{1, 2, 3, 4, 5, 6, 7}中可作为C(Y)的子集数目为 $\left(\begin{array}{c}7\\ 2\end{array}\right)+\left(\begin{array}{c}7\\ 3\end{array}\right)+\left(\begin{array}{c}7\\ 4\end{array}\right)+\left(\begin{array}{c}7\\ 5\end{array}\right)+\left(\begin{array}{c}7\\ 6\end{array}\right)+\left(\begin{array}{c}7\\ 7\end{array}\right)-16-20=84$ ，84个集合不能够区别出Y中的n个顶点，矛盾。

情形6： $u_1,u_2,\cdots ,u_{11}$ 的11个顶点颜色中互不相同的仅六种。不妨设 $f\left(u_i\right)=\left\{1,2,3,4,5,6\right\}\left(i=1,2,\cdots ,11\right)$ ，则每个 $C\left(v_j\right)$ 都不是2-子集，且每个 $C\left(v_j\right)$ 也都不是{1, 2, 3, 4, 5, 6}的3-子集、4-子集、5-子集、6-子集，

共有 $\left(\begin{array}{c}6\\ 3\end{array}\right)+\left(\begin{array}{c}6\\ 4\end{array}\right)+\left(\begin{array}{c}6\\ 5\end{array}\right)+\left(\begin{array}{c}6\\ 6\end{array}\right)=42$ 个，因此{1, 2, 3, 4, 5, 6, 7}可作为C(Y)的子集数目为 $\left(\begin{array}{c}7\\ 3\end{array}\right)+\left(\begin{array}{c}7\\ 4\end{array}\right)+\left(\begin{array}{c}7\\ 5\end{array}\right)+\left(\begin{array}{c}7\\ 6\end{array}\right)+\left(\begin{array}{c}7\\ 7\end{array}\right)-42=57$ ，57个集合不能够区别出Y中的n个顶点，矛盾。

因此，7种颜色不能够区别出 $K_{11,n}$ ，则当 $89\le n\le 212$ 时， ${\chi }_{vt}^e\left(K_{11,n}\right)\ge 8$。下面利用构造染色法，给出 $K_{11,n}$ 的一个8-VDET染色。

首先，确定f₂₁₂。X中顶点 $u_1,u_2,\cdots ,u_{11}$ 的色集合分别为：{1, 3, 4, 5, 7, 8}, {2, 3, 4, 5, 7, 8}, {1, 3, 4, 6, 7, 8}, {2, 3, 4, 6, 7, 8, {1, 3, 4, 5, 6, 7, 8}, {2, 3, 4, 5, 6, 7, 8}, {1, 2, 3, 4, 7, 8}, {1, 3, 4, 7, 8}, {1, 2, 3, 4, 5, 7, 8}, {1, 2, 3, 4, 6, 7, 8}, {1, 2, 3, 4, 5, 6, 7, 8}。且给X中 $u_1,u_2,\cdots ,u_{11}$ 11个顶点所染的颜色分别为1, 2, 1, 2, 1, 2, 1, 1, 2, 1, 2。

让由 $X\cup \left\{v_1,v_2,\cdots ,v_{212}\right\}$ 所导出的一个子图 $K_{11,88}$ 按照引理2给出的7-VDET染色f₈₈进行染色，然后给其它的顶点和关联边进行染色。将 $v_j\left(89\le j\le 104\right)$ 和它的关联边按照表1的方案进行染色(表1的第一行表示顶点 $u_i\left(1\le i\le 11\right)$ 的色集合不能染的颜色，第二行表示顶点 $u_i\left(1\le i\le 11\right)$ 所染的颜色，第三行的38 (3)表示顶点 $v_{89}$ 用3来染色，关联 $u_1{v}_{89},u_2{v}_{89},\cdots ,u_{11}{v}_{89}$ 分别用8, 8, 8, 8, 8, 8, 8, 8, 8, 8, 8来染色，并且顶点 $X\left(v_{89}\right)=\left\{3,8\right\}$ ，并且以此类推下去)。

将顶点 $v_j\left(105\le j\le 212\right)$ 分别对应色集合{1, 2, 3, 4, 5, 6, 7, 8}的全体含颜色8的2-、3-、4-、5-、6-、7-集合，但不是{1, 2, 8}, {3, 8}，也不是表1中任意一个顶点的色集合去染色。顶点 $v_j\left(105\le j\le 212\right)$ 及其它的关联边 $u_1{v}_j,u_2{v}_j,\cdots ,u_{11}{v}_j$ 的最优具体染色方案见表2。当 $89\le j\le 212$ 时， $K_{11,212}$ 的8-VDET染色f₂₁₂在由 $X\cup \left\{v_1,v_2,\cdots ,v_{88}\right\}$ 所导出的那个子图上的限制就是 $K_{11,j}$ 的8-VDET染色f_j。

表1. $K_{11,212}$ 顶点 $v_j\left(89\le j\le 104\right)$ 及其关联边的染色方案

表2. $K_{11,212}$ 顶点 $v_j\left(105\le j\le 212\right)$ 及其关联边的染色方案

4. 结语

根据反证法和分析法可以得到，当 $89\le n\le 212$ 时，用7种颜色不能对 $K_{11,212}$ 进行VDET染色。因此，当 $89\le n\le 212$ 时， ${\chi }_{vt}^e\left(K_{11,n}\right)\ge 8$。然后利用构造染色法，说明用8种颜色可以对 $K_{11,n}$ 进行点可区别E-全染色，从而可以得到 $K_{11,212}$ 的VDET色数是8。当 $n\ge 213$ 时，会对 $K_{11,n}$ 的VDET色数将继续进行研究。在后续的研究中，可继续利用反证法、结构分析法以及构造染色法等，讨论并给出相应的VDET色数，由于这个证明过程较长，此证略。

文章引用

汉大玮. 完全二部图K_11,n(89≤n≤212)的点可区别E-全染色
Vertex-Distinguishing E-Total Coloring of Complete Bipartite Graph K_11,n(89≤n≤212)[J]. 理论数学, 2022, 12(04): 572-579. https://doi.org/10.12677/PM.2022.124064

参考文献