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

收稿日期：2023年4月21日；录用日期：2023年5月23日；发布日期：2023年5月30日

摘要

通过构造以多重色集合和空集为元素的矩阵，应用组合分析法及构造具体染色的方法，得到了mC₇的点被多重色集合可区别的I-全染色和VI-全染色的全色数及最优染色方案。

关键词

mC₇，I-全染色，VI-全染色，多重集，色集合，点可区别

I-Total Coloring and VI-Total Coloring of mC₇ Which Are Vertex-Distinguishing by Multiple Sets

Nana Wang

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

Received: Apr. 21^st, 2023; accepted: May 23^rd, 2023; published: May 30^th, 2023

ABSTRACT

By use of the method of constructing a matrix whose entries are the suitable multiple sets or empty sets and the method of distributing color set in advance, we will give the optimal I-(VI-) total colorings of mC₇ which are vertex­distinguished by multiple sets in this paper. Thereby, we obtain I-(VI-) total chromatic numbers of mC₇ which are vertex-distinguished by multiple sets.

Keywords:mC7, I-Total Coloring, VI-Total Coloring, Multiset, Color Set, Vertex-Distinguishing

Copyright © 2023 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. 引言及准备工作

本文所探讨的图均为有限简单无向图。关于图的点可区别正常边染色与图的点可区别一般边染色目前已有较多结论 [1] - [7] 。2008年，Zhang等 [8] 提出了点可区别的全染色及相关猜想，图的点可区别I-全染色及相关猜想由Chen等 [9] 在2014年给出。对于图在非多重集上的点可区别的未必正常的全染色已有许多研究成果 [10] [11] [12] 。本文考虑图在多重集上的点可区别的一类未必正常全染色。

设 $f:V\cup E\to \left\{1,2,\cdots ,l\right\}$ 为图G的一个一般全染色(未必正常)。若对 $\forall u,v\in V$ ， $u,v$ 相邻，有 $f\left(u\right)\ne f\left(v\right)$ ，且对 $uv,vw\in E$ ， $uv\ne vw$ ，有 $f\left(uv\right)\ne f\left(vw\right)$ ，则称该染色f为图G的I-全染色。若在f下图G的任意两条相邻边染以不同颜色，则称f为VI-全染色。显然I-全染色是VI-全染色。图G使用了l种颜色的I-全染色(VI-全染色)，称为图G的l-I-全染色(l-VI-全染色)。这里需要注意是，在本文中这样表述时总认为所使用的颜色是 $\left\{1,2,\cdots ,l\right\}$ 。

设f为图G的一般全染色。对 $\forall x\in \text{V}\left(G\right)$ ，将 ${\tilde{C}}_f\left(x\right)$ 或 $\tilde{C}\left(x\right)$ (不引起混淆时)称为点x的多重色集合，是由点x的颜色和点x关联的边的颜色构成。显然有 $\left|{\tilde{C}}_f\left(x\right)\right|=d_G\left(x\right)+1$ ，若称f是点被多重色集合可区别的，则是指 $\forall u,v\in G$ ，总有 $\tilde{C}\left(u\right)\ne \tilde{C}\left(v\right)$ 。令

${\tilde{\chi }}_{\text{vt}}^{\text{i}}\left(G\right)=\min \left\{l|G存在点被多重色集合可区别的l\text{-I-}全染色\right\}$ ，

${\tilde{\chi }}_{\text{vt}}^{\text{vi}}\left(G\right)=\min \left\{l|G存在点被多重色集合可区别的l\text{-VI-}全染色\right\}$ 。

将 ${\tilde{\chi }}_{\text{vt}}^{\text{i}}\left(G\right)$ 称为点被多重色集合可区别的l-I-全色数，将 ${\tilde{\chi }}_{\text{vt}}^{\text{vi}}\left(G\right)$ 称为点被多重色集合可区别的l-VI-全色数。用 $n_i\left(G\right)$ 表示图G的度为i的顶点的个数， $\delta \le i\le \Delta$ ，这里 $\delta$ 和 $\Delta$ 分别表示图G的最小度和最大度。规定

$\tilde{\zeta }\left(G\right)=\min \left\{l|i\left(\begin{array}{c}l\\ i\end{array}\right)+\left(\begin{array}{c}l\\ i+1\end{array}\right)\ge n_i,\delta \le i\le \Delta \right\}$ 。

上式中加号前面的项表示点的色是其关联边的颜色之一， $\left(\begin{array}{c}l\\ i\end{array}\right)$ 表示从l种互异的颜色中取出i种互不相同的颜色的取法数，对每种这样的取法，点的色的取法共有i种，因此共有 $i\left(\begin{array}{c}l\\ i\end{array}\right)$ 种；加号后面的项表示点的色不是其关联边的颜色，此时点的多重色集合里的 $i+1$ 种颜色互不相同，具有这种特点的 $i+1$ -子集，共有 $\left(\begin{array}{c}l\\ i+1\end{array}\right)$ 个。

引理1 ${\tilde{\chi }}_{\text{vt}}^{\text{i}}\left(G\right)\ge {\tilde{\chi }}_{\text{vt}}^{\text{vi}}\left(G\right)\ge \tilde{\zeta }(\; G\; )$

证明令 $s={\tilde{\chi }}_{\text{vt}}^{\text{i}}\left(G\right)$ 。图G中存在使用了s种色的点被多重色集合可区别的I-全染色，而它也是图G的使用了s种色的点被多重色集合可区别的VI-全染色。故 $s\in \left\{k\right|G$ 存在点被多重色集合可区别的k-VI-全染色}。而

${\tilde{\chi }}_{\text{vt}}^{\text{vi}}\left(G\right)=\min \left\{k|G存在点被多重色集合可区别的k\text{-VI-}全染色\right\}$ ，

因此 ${\tilde{\chi }}_{\text{vt}}^{\text{vi}}\left(G\right)\le s$ 。即 ${\tilde{\chi }}_{\text{vt}}^{\text{vi}}\left(G\right)\le {\tilde{\chi }}_{\text{vt}}^{\text{i}}\left(G\right)$ 。

再令 $t={\tilde{\chi }}_{\text{vt}}^{\text{vi}}\left(G\right)$ 。则图G存在使用了t种色的点被多重色集合可区别的VI-全染色。从而对 $\delta \le i\le \Delta$ ，考虑度为i的顶点，我们有

$i\left(\begin{array}{c}t\\ i\end{array}\right)+\left(\begin{array}{c}t\\ i+1\end{array}\right)\ge n_i$ .

所以 $t\in \left\{l|i\left(\begin{array}{c}l\\ i\end{array}\right)+\left(\begin{array}{c}l\\ i+1\end{array}\right)\ge n_i,\delta \le i\le \Delta \right\}$ 。故 $t\ge \tilde{\zeta }\left(G\right)$ ，即 ${\tilde{\chi }}_{\text{vt}}^{\text{vi}}\left(G\right)\ge \tilde{\zeta }\left(G\right)$ ，得证。

为了在定理证明过程中构造最优的点被多重色集合可区别的I-全染色和VI-全染色的方便，我们先定义一类矩阵。对任意的 $l\ge 4$ ，构造 $l\times \left(l-1\right)$ 矩阵 $A_{l\times \left(l-1\right)}$ ，使矩阵 $A_{l\times \left(l-1\right)}$ 的元素是集合 $\left\{1,2,\cdots ,l\right\}$ 的含l的多重3-子集或空集，其中第i列含有 $i-1$ 个 $\varnothing$ ：

$A_{l\times \left(l-1\right)}=\left(\begin{array}{cccccc}\left\{1,1,l\right\}& \left\{2,2,l\right\}& \left\{3,3,l\right\}& \cdots & \left\{l-2,l-2,l\right\}& \left\{l-1,l-1,l\right\}\\ \left\{1,2,l\right\}& \left\{2,3,l\right\}& \left\{3,4,l\right\}& \cdots & \left\{l-2,l-1,l\right\}& \left\{l-1,l,l\right\}\\ ⋮& ⋮& ⋮& & ⋮& ⋮\\ \left\{1,l-1,l\right\}& \left\{2,l,l\right\}& \varnothing & \cdots & \varnothing & \varnothing \\ \left\{1,l,l\right\}& \varnothing & \varnothing & \cdots & \varnothing & \varnothing \end{array}\right)$

图1. 一个C₇的全染色

将如图1所示的C₇的全染色记为： $a,b,c,d,e,f,g,h,i,j,k,l,m,n$ 。

对于C₇的点被多重色集合可区别的I-全染色，据 $A_{l\times \left(l-1\right)}$ 定义为如下四种分类：

类型I当 $j\equiv 1\left(\mathrm{mod}2\right)$ 时，若 $A_{l\times \left(l-1\right)}$ 中存在 $\left\{j,j,l\right\},\left\{j,l-2,l\right\},\left\{j,l-1,l\right\},\left\{j,l,l\right\},\left\{j+1,j+1,l\right\},\{j+1,$ $l-1,l\},\left\{j+1,l,l\right\}$，这7个3-子集是某个C₇的点被多重色集合可区别的l-I-全染色下的各顶点的色集合，其染色方案为 $l,j,j,l,l,j+1,j+1,l,l,j+1,l-1,l,j,l-2$ 。

类型II当l为奇数时， $A_{l\times \left(l-1\right)}$ 的第 $l-1,l-2,l-3,l-4$ 列的7个3-子集 $\left\{l-1,l-1,l\right\},\left\{l-1,l,l\right\},\{l-2,$ $l-2,l\},\left\{l-2,l-1,l\right\},\left\{l-2,l,l\right\},\left\{l-3,l-2,l\right\},\left\{l-4,l-3,l\right\}$ ，恰是一个C₇的点被多重色集合可区别的l-I-全染色下的各顶点的色集合，其染色方案为 $l,l-2,l-2,l,l,l-1,l-1,l,l,l-1,l-2,l,l-3,l-4$ ；当l为偶数时， $A_{l\times \left(l-1\right)}$ 的第 $l-1,l-4,l-5,l-6,l-7$ 列的14个3-子集可对2个C₇进行点被多重色集合可区别的l-I-全染色，其分别为 $\left\{\left\{l-1,l-1,l\right\},\left\{l-1,l,l\right\},\left\{l-4,l-3,l\right\},\left\{l-4,l-2,l\right\},\left\{l-5,l-4,l\right\},\left\{l-5,l-3,l\right\},\left\{l-6,l-2,l\right\}\right\}$ 所对应的染色方案为 $l,l-1,l-1,l,l,l-6,l-2,l-4,l,l-3,l-4,l,l-5,l-3$ ； $\{\left\{l-7,l-6,l\right\},\left\{l-7,l-5,l\right\},\{l-7,$ $l-4,l\},\left\{l-7,l-3,l\right\},\left\{l-6,l-5,l\right\},\left\{l-6,l-4,l\right\},\left\{l-6,l-3,l\right\}\}$ 所对应的染色方案为 $l,l-6,l-7,l-5,l,l-4,$ $l-6,l-5,l,l-6,l-3,l,l-7,l-4$。

类型III 当 $i\equiv 2\left(\mathrm{mod}7\right),j\equiv 1\left(\mathrm{mod}2\right)$ 时，若 $A_{l\times \left(l-1\right)}\left(i,i+1,i+2,i+3,i+4,i+5,i+6|j,j+1\right)$ 中的14个3-子集都非空，则可对2个C₇进行点被多重色集合可区别的l-I-全染色，其分别为 $\{\left\{j,j+i-1,l\right\},\left\{j,j+i,l\right\},$ $\left\{j,j+i+1,l\right\},\left\{j,j+i+2,l\right\},\left\{j+1,j+i,l\right\},\left\{j+1,j+i+1,l\right\},\left\{j+1,j+i+2,l\right\}\}$，所对应的染色方案为 $l,j+i$ $-1,j,j+i,l,j+i+1,j+1,j+i,l,j+1,j+i+2,l,j,j+i+1$； $\{\left\{j,j+i+3,l\right\},\left\{j,j+i+4,l\right\},\left\{j,j+i+5,l\right\},\{j+1,$ $j+i+3,l\},\left\{j+1,j+i+4,l\right\},\left\{j+1,j+i+5,l\right\},\left\{j+1,j+i+6,l\right\}\}$ 所对应的染色方案为 $l,j+i+4,j,j+i+5,l,$ $j+i+6,j+1,j+i+5,l,j+i+4,j+1,l,j+i+3,j$。

类型IV $A_{l\times \left(l-1\right)}$ 经类型I，类型II，类型III的染色划分后，当 $i-1\equiv 1\left(\mathrm{mod}7\right),j\equiv 1\left(\mathrm{mod}2\right)$ ，则有如下3种类似类型III的分类。下述3种情形中两个子矩阵中的 $i,j$ 均不同，为表区分我们把第二个子矩阵中的 $i,j$ 记为 $i_d,j_d$ 。

情形Ⓐ，若 $A_{l\times (l-1)}$ 中同时存在 $A_{l\times \left(l-1\right)}\left(i,i+1,i+2,i+3,i+4,i+6|j,j+1\right)$ ， $A_{l\times \left(l-1\right)}\left(i_d|j_d,j_d+1\right)$ ，这两个子矩阵中的14个3-子集恰是2个C₇的点被多重色集合可区别的l-I-全染色，其分别为 $\{\left\{j,l-8,l\right\},\left\{j,l-7,l\right\},$ $\left\{j,l-6,l\right\},\left\{j,l-5,l\right\},\left\{j+1,l-7,l\right\},\left\{j+1,l-6,l\right\},\left\{j+1,l-5,l\right\}\}$ 所对应的染色方案为 $l,l-8,j,l-7,l,l-6,$ $j+1,l-7,l,j+1,l-5,l,j,l-6$； $\{\left\{j,l-4,l\right\},\left\{j,l-3,l\right\},\left\{j+1,l-4,l\right\},\left\{j+1,l-3,l\right\},\left\{j+1,l-2,l\right\},\left\{j_d,l-3,l\right\},$ $\left\{j_d+1,l-2,l\right\}\}$ 所对应的染色方案为 $l,l-4,j,l-3,l,j_d+1,l-2,j+1,l,l-4,j+1,l,l-3,j_d$ 。

情形Ⓑ，若 $A_{l\times \left(l-1\right)}$ 中同时存在 $A_{l\times \left(l-1\right)}\left(i,i+1,i+2,i+3,i+4|j,j+1\right)$ ， $A_{l\times \left(l-1\right)}\left(i_d,i_d+1|j_d,j_d+1\right)$ ，这两个子矩阵中的14个3-子集恰是2个C₇的点被多重色集合可区别l-I-全染色，其分别为 $\{\left\{j,l-7,l\right\},\left\{j,l-6,l\right\},$ $\left\{j,l-5,l\right\},\left\{j,l-4,l\right\},\left\{j+1,l-6,l\right\},\left\{j+1,l-5,l\right\},\left\{j+1,l-4,l\right\}\}$ 所对应的染色方案为 $l,l-7,j,l-6,l-5,j$ $+1,l-6,l,j+1,l-4,l,j,l-5$； $\{\left\{j,l-3,l\right\},\left\{j+1,l-3,l\right\},\left\{j+1,l-2,l\right\},\left\{j_d,l-5,l\right\},\left\{j_d,l-4,l\right\},\left\{j_d+1,l-4,l\right\},$ $\left\{j_d+1,l-3,l\right\}\}$ 所对应的染色方案为 $l,l-2,j+1,l,l-3,j,l,l-5,j_d,l-4,l,l-3,j_d+1,l-4$ 。

情形Ⓒ，若 $A_{l\times \left(l-1\right)}$ 中同时存在 $A_{l\times \left(l-1\right)}\left(i,i+1,i+2,i+3|j,j+1\right)$ ， $A_{l\times \left(l-1\right)}\left(i_d,i_d+1,i_d+1|j_d,j_d+1\right)$ ，这两个子矩阵中的14个3-子集恰是2个C₇的点被多重色集合可区别l-I-全染色，其分别为 $\{\left\{j,l-6,l\right\},\left\{j,l-5,l\right\},$ $\left\{j,l-4,l\right\},\left\{j,l-3,l\right\},\left\{j+1,l-5,l\right\},\left\{j+1,l-4,l\right\},\left\{j+1,l-3,l\right\}\}$ 所对应的染色方案为 $l,l-6,j,l-5,l,l-4,j$ $+1,l-5,l,j+1,l-3,l,j,l-4$； $\{\left\{j+1,l-2,l\right\},\left\{j_d,l-5,l\right\},\left\{j_d,l-4,l\right\},\left\{j_d,l-3,l\right\},\left\{j_d+1,l-4,l\right\},\left\{j_d+1,l-3,l\right\},$ $\left\{j_d+1,l-2,l\right\}\}$ 所对应的染色方案为 $l,j+1,l-2,j_d+1,l,l-4,j_d,l-5,l,j_d,l-3,l,j_d+1,l-4$ 。

2. 主要结果及其证明

定理1 若 $2\left(\begin{array}{c}l-1\\ 2\end{array}\right)+\left(\begin{array}{c}l-1\\ 3\end{array}\right)<7m\le 2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right),m\ge 1,l\ge 4$ ，则 ${\tilde{\chi }}_{\text{vt}}^{\text{i}}\left(m{C}_7\right)=l$ 。

证明显然有 $l=\tilde{\zeta }\left(m{C}_7\right)\le {\tilde{\chi }}_{\text{vt}}^{\text{i}}\left(G\right)$ ，因此我们可直接对mC₇进行点被多重色集合可区别的l-I-全染色。

① $l=3$ 的3-子集有 $\left\{1,1,2\right\},\left\{1,2,2\right\},\left\{1,1,3\right\},\left\{1,3,3\right\},\left\{2,2,3\right\},\left\{2,3,3\right\},\left\{1,2,3\right\}$ ，这7个3-子集不能对一个C₇进行点被多重色集合可区别的3-I-全染色。

证明反证法。假设C₇存在点被多重色集合可区别的3-I-全染色f。

1) f存在一种颜色只染一条边，另两种颜色都各染3条边，不妨设3只染了一条边，而1，2都各染3条边。如图2所示， ${\upsilon }_1,{\upsilon }_2,{\upsilon }_3,{\upsilon }_4,{\upsilon }_5$ 在f下的色集合只可能是3种： $\left\{1,1,2\right\},\left\{1,2,2\right\},\left\{1,2,3\right\}$ 。矛盾。

2) f中每种颜色都至少染2条边，不妨设1，3都染两条边，而2染了3条边。有如下两种情形：

a) 如图3所示， ${\upsilon }_1,{\upsilon }_2,{\upsilon }_7$ 的色集合只能是 $\left\{1,1,2\right\},\left\{1,2,2\right\},\left\{1,2,3\right\}$ (不计顺序)， $\left\{1,2,3\right\}$ 必是 ${\upsilon }_1,{\upsilon }_2,{\upsilon }_7$ 其中之一的色集合， $\left\{1,2,3\right\}$ 必不是 ${\upsilon }_3,{\upsilon }_4,{\upsilon }_5$ 的色集合。那么 ${\upsilon }_3,{\upsilon }_4,{\upsilon }_5$ 中必有2个点的色集合相同。矛盾。

b) 如图4所示， ${\upsilon }_3,{\upsilon }_4,{\upsilon }_7$ 其中之一的色集合为 $\left\{1,2,3\right\}$ ， ${\upsilon }_1,{\upsilon }_2,{\upsilon }_5$ 其中之一的色集合为 $\left\{1,2,3\right\}$ 。矛盾。

综上，C₇不存在点被多重色集合可区别的3-I-全染色。

图2. 一个C₇的染色

图3. 一个C₇的染色

图4. 一个C₇的染色

② 当 $m=2$ 时， $l=4$ 。用 $\left\{1,1,2\right\},\left\{1,2,2\right\},\left\{1,1,3\right\},\left\{2,2,3\right\},\left\{2,3,3\right\},\left\{1,2,3\right\},\left\{2,3,4\right\}$ 给第一个C₇进行染色即染色为 $2,4,3,2,2,1,1,2,2,3,3,1,1,3$ 。用 $\left\{1,3,3\right\},\left\{1,1,4\right\},\left\{1,2,4\right\},\left\{1,3,4\right\},\left\{2,2,4\right\},\left\{2,4,4\right\},\left\{3,4.4\right\}$ 给第二个C₇即染色为 $1,3,3,4,4,2,2,4,4,3,1,1,4,2$ 。于是将多重3-子集 $\left\{1,4,4\right\},\left\{3,3,4\right\}$ 剩余。

③ 当 $3\le m\le 4$ 时， $l=5$ 。在2C₇的基础上，下面我们从第3个C₇开始进行染色。由类型I知A₅可对1个C₇用染色方案 $5,1,1,5,5,2,2,5,5,2,4,5,1,3$ 进行染色，由类型II知A₅可对1个C₇用染色方案 $5,3,3,5,5,$ $4,4,5,5,4,3,5,2,1$ 进行染色。上述染色中用完了 $\left\{1,2,3,4,5\right\}$ 中含5的多重3-子集，此时仍有多重3-子集 $\left\{1,4,4\right\},\left\{3,3,4\right\}$ 剩余。

④ 当 $5\le m\le 7$ 时， $l=6$ 。在上一步染色基础上我们从第5个C₇开始进行染色。由类型I知A₆可对2个C₇分别用染色方案 $6,1,1,6,6,2,2,6,6,2,5,6,1,4$ 和 $6,3,3,6,6,4,4,6,6,4,5,6,3,4$ 去染。此时A₆的剩余元素有 $\left\{1,2,6\right\},\left\{1,3,6\right\},\left\{2,3,6\right\},\left\{2,4,6\right\},\left\{5,5,6\right\},\left\{5,6,6\right\}$ 。将其与②遗留的 $\left\{3,3,4\right\}$ 组合用染色方案 $6,5,5,6,6,1,2,3,$ $6,2,4,3,3,1$ 对第7个C₇进行染色。上述染色中用完了 $\left\{1,2,3,4,5,6\right\}$ 中含6的多重3-子集，此时仍有多重3-子集 $\left\{1,4,4\right\}$ 剩余。

⑤ 当 $8\le m\le 11$ 时， $l=7$ 。在前7C₇的点被多重色集合可区别I-全染色的基础上，下面对第8个C₇到第11个C₇进行染色。由类型I和类型II知A₇可对3个C₇分别用染色方案 $7,1,1,7,7,2,2,7,7,2,6,7,1,5$ ； $7,3,3,7,7,4,4,7,7,4,6,7,3,5$ 和 $7,5,5,7,7,6,6,7,7,6,5,7,4,3$ 去染。此时有3-子集 $\left\{1,2,7\right\},\left\{1,3,7\right\},\left\{1,4,7\right\},\{2,3,$ $7\},\left\{2,4,7\right\},\left\{2,5,7\right\}$ 剩余，将其与②遗留的 $\left\{1,4,4\right\}$ 组合用染色方案 $7,2,1,4,7,3,2,5,7,2,4,1,1,3$ 对第11个C₇进行染色。至此，用完了 $\left\{1,2,3,4,5,6,7\right\}$ 的所有多重3-子集。

⑥ 当 $12\le m\le 16$ 时， $l=8$ 。在前11C₇的点被多重色集合可去别I-全染色的基础上从第12个C₇开始进行染色。由类型I和类型II知A₈可对5个C₇分别用染色方案 $8,1,1,8,8,2,2,8,8,2,7,8,1,6$ ； $8,3,3,8,8,4,4,8,8,$ $4,7,8,3,6$； $8,5,5,8,8,6,6,8,8,5,7,8,6,5$ ； $8,2,1,3,8,4,2,3,8,2,5,8,1,4$ 和 $8,7,7,8,8,2,6,4,8,5,4,8,3,5$ 去染。此时用完了 $\left\{1,2,3,4,5,6,7,8\right\}$ 的所有多重3-子集。

⑦ l是从1到它的整数(全文亦然)，让l从9开始递增，并且递归地进行如下过程。在已构造好的 $\lfloor \frac{1}{7}\left[2\left(\begin{array}{c}l-1\\ 2\end{array}\right)+\left(\begin{array}{c}l-1\\ 3\end{array}\right)\right]\rfloor C_7$ 的点被多重色集合可区别 $l-1$ -I-全染色的基础上，对第 $\lfloor \frac{1}{7}\left[2\left(\begin{array}{c}l-1\\ 2\end{array}\right)+\left(\begin{array}{c}l-1\\ 3\end{array}\right)\right]\rfloor +1$ 个C₇到第 $\lfloor \frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)\right]\rfloor$ 个C₇的染色方案叙述如下。

当 $l\equiv 2\left(\mathrm{mod}7\right),l\ge 9$ 时。由类型I，类型II，类型III，类型IV可以得到 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)-16\right]$ $C_{\text{7}}$ 的点被多重色集合可区别的l-I-全染色，并且除 $\left\{3,l-3,l\right\},\left\{4,l-2,l\right\}$ 之外用完了 $\left\{1,2,\cdots ,l\right\}$ 的其余所有多重3-子集。

当 $l\equiv 3\left(\mathrm{mod}7\right),l\ge 10$ 时。由类型I，类型II，类型III，类型IV可以得到 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)-14\right]$ $C_{\text{7}}$ 的点被多重色集合可区别的l-I-全染色，除第1，2列的剩余元素及前述 $\left\{3,l-4,l-1\right\},\left\{4,l-3,l-1\right\}$ 之外，用完了 $\left\{1,2,\cdots ,l\right\}$ 的其余所有多重3-子集。用 $\left\{1,l-8,l\right\},\left\{1,l-7,l\right\},\left\{1,l-6,l\right\},\left\{1,l-5,l\right\},\left\{2,l-7,l\right\},\left\{2,l-6,l\right\},$ $\left\{2,l-5,l\right\}$ 对第 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)-7\right]$ 个C₇进行I-全染色，染色方案为 $1,l-8,l,2,l-7,1,l,2,l-6,1,l,2,l-5,l$ 。用 $\left\{1,l-4,l\right\},\left\{1,l-3,l\right\},\left\{2,l-4,l\right\},\left\{2,l-3,l\right\},\left\{2,l-2,l\right\}$ 与 $\left\{3,l-4,l-1\right\},\left\{4,l-3,l-1\right\}$ 对第 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)\right]$ 个C₇进行I-全染色，染色方案为 $l-4,3,l-1,4,l-3,2,l,l-4,1,l-3,l,l-2,2,l$ 。此时得到了 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)\right]$ $C_{\text{7}}$ 的点被多重色集合可区别的l-I-全染色。

当 $l\equiv 4\left(\mathrm{mod}7\right),l\ge 11$ 时。由类型I，类型II，类型III，类型IV可以得到 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)-2\right]$ $C_{\text{7}}$ 的点被多重色集合可区别的l-I-全染色，除 $\left\{5,l-3,l\right\},\left\{6,l-2,l\right\}$ 之外用完了 $\left\{1,2,\cdots ,l\right\}$ 的其余所有多重3-子集。

当 $l\equiv 5\left(\mathrm{mod}7\right),l\ge 12$ 时。由类型I，类型II，类型III，类型IV可以得到 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)-2\right]$ $C_{\text{7}}$ 的点被多重色集合可区别的l-I-全染色，除上述剩余的 $\left\{5,l-4,l-1\right\},\left\{6,l-3,l-1\right\}$ 之外用完了 $\left\{1,2,\cdots ,l\right\}$ 的其余所有多重3-子集。

当 $l\equiv 6\left(\mathrm{mod}7\right),l\ge 13$ 时。由类型I，类型II，类型III，类型IV可以得到 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)-8\right]$ $C_{\text{7}}$ 的点被多重色集合可区别的l-I-全染色，除第7，8列的剩余元素及前述 $\left\{5,l-5,l-2\right\},\left\{6,l-4,l-2\right\}$ 之外，用完了 $\left\{1,2,\cdots ,l\right\}$ 的其余所有多重3-子集。对第 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)-1\right]$ 个C₇用 $\left\{7,l-5,l\right\},\left\{7,l-4,l\right\},\left\{7,l-3,l\right\},\{8,l-4,$ $l\},\left\{8,l-3,l\right\},\left\{8,l-2,l\right\}$与 $\left\{5,l-5,l-2\right\}$ 进行I-全染色，染色方案为 $l-2,5,l-5,7,l,l-4,7,l-3,l,l-4,8,l-3,$ $l,8$。此时得到了 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)-1\right]$ $C_{\text{7}}$ 的点被多重色集合可区别的l-I-全染色。

当 $l\equiv 0\left(\mathrm{mod}7\right),l\ge 14$ 时。由类型I，类型II，类型III，类型IV可以得到 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)-7\right]$ $C_{\text{7}}$ 的点被多重色集合可区别的l-I-全染色，除第1，2列的剩余元素及前述剩下的 $\left\{6,l-5,l-3\right\}$ 外用完了 $\left\{1,2,\cdots ,l\right\}$ 的其余所有多重3-子集。对第 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)\right]$ 个C₇用 $\left\{6,l-5,l-3\right\}$ 与 $\left\{1,l-5,l\right\},\left\{1,l-4,l\right\},\left\{1,l-3,l\right\},\{2,l-4,$ $l\},\left\{2,l-3,l\right\},\left\{2,l-2,l\right\}$ 进行I-全染色，染色方案为 $l-5,6,l-3,1,l,l-3,2,l-2,l,1,l-4,2,l,1$ 。至此，得到了 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)\right]$ $C_{\text{7}}$ 的点被多重色集合可区别的l-I-全染色。

当 $l\equiv 1\left(\mathrm{mod}7\right),l\ge 15$ 时。由类型I，类型II，类型III，类型IV可以得到 $\frac{1}{7}\left[2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right)\right]$ $C_{\text{7}}$ 的点被多重色集合可区别的l-I-全染色，并且用完了 $\left\{1,2,\cdots ,l\right\}$ 的所有多重3-子集。

定理证毕。

定理2 若 $2\left(\begin{array}{c}l-1\\ 2\end{array}\right)+\left(\begin{array}{c}l-1\\ 3\end{array}\right)<7m\le 2\left(\begin{array}{c}l\\ 2\end{array}\right)+\left(\begin{array}{c}l\\ 3\end{array}\right),m\ge 1,l\ge 4$ ，则 ${\tilde{\chi }}_{\text{vt}}^{\text{vi}}\left(m{C}_7\right)=l$ 。

证明由引理1及定理1立得此结论。

文章引用

王娜娜. mC7的点被多重色集合可区别的I-全染色和VI-全染色
I-Total Coloring and VI-Total Coloring of mC7 Which Are Vertex-Distinguishing by Multiple Sets[J]. 理论数学, 2023, 13(05): 1381-1388. https://doi.org/10.12677/PM.2023.135141

参考文献