路和完全图的乘积图的广义染色数

The Generalized Coloring Number of Product Graph of Path and Complete Graph

摘要: 本文讨论的是路与完全图的乘积图，我们给出了路与完全图的乘积图的一个线性序，并且在该线性序下分别给出了路与完全图的直积图、笛卡尔积图以及强积图的广义染色数上界。

Abstract: This article discusses the product graph of a path and complete graph. We provide a linear order for the product graph of a path and complete graph, and under this linear order, we respectively give the upper bounds on the generalized coloring number of the direct product graph, Cartesian product graph and strong product graph of the path and complete graph.

1. 引言

2003年，Kierstead和Yang [1]提出了广义染色数的概念，它是许多图论研究方向的重要工具。乘积图也是许多学者广泛关注的一类图，许多复杂的图类往往可以放在一些简单图类的乘积图中进行研究。本文将对路和完全图的乘积图的广义染色数进行研究，通过指定该乘积图的线性序从而依次给出在该线性序下路和完全图的直积图、笛卡尔积图以及强积图的广义染色数上界。

首先我们介绍广义染色数的概念。对一个图G，令$\prod \left(G\right)$ 是$V\left(G\right)$ 所有线性序的集合，$L\in \prod \left(G\right)$ 。令x和y是图G的两个顶点，如果$x{\prec }_{L}y$ 并且存在一条从y到x长度最多为k的路P使得对路上所有的内点z满足$y{\prec }_{L}z$ 则我们称x是从y强k-可达的顶点，如果P上所有的内点z满足$x{\prec }_{L}z$ 则我们称x是从y弱k-可达的顶点。令$R_k\left(G_L,y\right)$ 是所有从y强k-可达的顶点集，$Q_k\left(G_L,y\right)$ 是所有从y弱k-可达的顶点集，且$R_k\left[G_L,y\right]=R_k\left(G_L,y\right)\cup \left\{y\right\}$ ，同理$Q_k\left[G_L,y\right]=Q_k\left(G_L,y\right)\cup \left\{y\right\}$ 。定义图G的强k-染色数，记作$co{l}_k\left(G\right)$ 和弱k-染色数，记作$wco{l}_k\left(G\right)$ 分别为：

$co{l}_k\left(G\right)=\underset{L\in \prod \left(G\right)}{\min }\underset{v\in V\left(G\right)}{\max }\left|R_k\left[G_L,v\right]\right|$ 和

$wco{l}_k\left(G\right)=\underset{L\in \prod \left(G\right)}{\min }\underset{v\in V\left(G\right)}{\max }\left|Q_k\left[G_L,v\right]\right|$

图G强k-染色数与弱k-染色数之间的关系如下[1]：$co{l}_k\left(G\right)\le wco{l}_k\left(G\right)\le {\left(co{l}_k\left(G\right)\right)}^k$ 。

下面我们来依次介绍笛卡尔积图、直积图、强积图的概念。

图A和图B的笛卡尔积(记作$A\square B$ )由点集$V\left(A\right)\times V\left(B\right)$ 组成，其中不同的点$\left(v,x\right)$ ，$\left(w,y\right)\in V\left(A\right)\times V\left(B\right)$ 相邻当且仅当满足：(1) $v=w$ 且$xy\in E\left(B\right)$ 或(2) $x=y$ 且$vw\in E\left(A\right)$ 。

图A和图B的直积(记作$A\times B$ )由点集$V\left(A\right)\times V\left(B\right)$ 组成，其中不同的点$\left(v,x\right)$ ，$\left(w,y\right)\in V\left(A\right)\times V\left(B\right)$ 相邻当且仅当满足：$vw\in E\left(A\right)$ 且$xy\in E\left(B\right)$ 。

图A和图B的强积(记作$A⊠B$ )由点集$V\left(A\right)\times V\left(B\right)$ 组成，其中不同的点$\left(v,x\right)$ ，$\left(w,y\right)\in V\left(A\right)\times V\left(B\right)$ 相邻当且仅当满足：(1) $v=w$ 且$xy\in E\left(B\right)$ 或(2) $x=y$ 且$vw\in E\left(A\right)$ 或(3) $vw\in E\left(A\right)$ 且$xy\in E\left(B\right)$ 。

由上述三种乘积的定义可知：图A和图B的笛卡尔积图、直积图和强积图的顶点集是相同的，并且图A和图B的强积图的边集是图A和图B的笛卡尔积图的边集和直积图的边集不相交的并。

2020年，V. Dujmović，G. Joret，P. Micek，P. Morin，T. Ueckerdt和D. R. Wood给出如下平面图的乘积结构。

定理1 [2]每个平面图都是以下乘积图的子图：

(1) $H⊠P$ ，其中H是树宽小于等于8的平面图，P为一条路。

(2) $H⊠P⊠K_3$ ，其中H是树宽小于等于3的平面图，P为一条路。

在[3]中，作者给出了关于树和路的乘积图的广义染色数上界。

定理2 [3]对于所有的整数$k>0$ ，如果图$G=T\times P$ ，其中T是一棵树，P是一条路，那么$wco{l}_k\left(G\right)\le k^2+k+1$ 。$co{l}_k\left(G\right)\le k+2$ 。

定理3 [3]对于所有的整数$k>0$ ，如果图$G=T\square P$ ，其中T是一棵树，P是一条路，那么$wco{l}_k\left(G\right)\le k^2+k+1$ 。$0<k\le 2$ 时，$co{l}_k\left(G\right)\le 3$ ；$k>2$ 时，$co{l}_k\left(G\right)\le 2k-1$ 。

定理4 [3]对于所有的整数$k>0$ ，如果图$G=T⊠P$ ，其中T是一棵树，P是一条路，那么$wco{l}_k\left(G\right)\le 2k^2+k+1$ 。$co{l}_k\left(G\right)\le 2k+3$ 。

2. 路和完全图的乘积图的广义染色数

令$P_n$ 为一条长为n的路，$K_m$ 为m个顶点的完全图。假设$m,n$ 均为足够大的有限正整数，下面我们首先给出$P_n$ 与$K_m$ 乘积图的顶点线性序，进而根据乘积图的特点给出该乘积图的广义染色数的上界。

定理5 对于所有的整数$k>0$ ，如果图$G=P_n\times K_m$ ，其中$P_n$ 为一条长为n的路，$K_m$ 为m个顶点的完全图，则$wco{l}_k\left(G\right)\le \lfloor k/2\rfloor +\left(m-1\right)\lceil k/2\rceil +1$ 。当$k=1$ 时，$co{l}_k\left(G\right)\le m$ ；当$k=2$ 时，$co{l}_k\left(G\right)\le 2m-1$ ；当$k\ge 3$ 时，$co{l}_k\left(G\right)\le 2m$ 。

证明 对于路$P_n$ ，我们用$\sigma$ 来记作它的一个线性序$\left(u_1,u_2,\cdots ,u_n\right)$ ，对于完全图$K_m$ ，我们用$\phi$ 来记作它的一个线性序$\left(v_1,v_2,\cdots ,v_m\right)$ ，对于图$G=P_n\times K_m$ 的顶点集$V\left(G\right)=\left(\left(u_1,v_1\right),\left(u_1,v_2\right),\cdots ,\left(u_1,v_m\right),\left(u_2,v_1\right),\cdots ,\left(u_2,v_m\right),\cdots ,\left(u_n,v_1\right),\cdots ,\left(u_n,v_m\right)\right)$ 。令L为图G的一个线性序，我们按照如下的方式给定线性序L：对于图G中的任意两个点$\left(u_i,v_j\right)$ 和$\left(u_{i^{\prime }},v_{j^{\prime }}\right)$ 。

1. 如果$u_i\ne u_{i^{\prime }}$ ，则$\left(u_i,v_j\right){\prec }_L\left(u_{i^{\prime }},v_{j^{\prime }}\right)$ 当且仅当$u_i{\prec }_{\sigma }{u}_{i^{\prime }}$ 。

2. 如果$u_i=u_{i^{\prime }}$ ，则$\left(u_i,v_j\right){\prec }_L\left(u_{i^{\prime }},v_{j^{\prime }}\right)$ 当且仅当$v_j{\prec }_{\phi }{v}_{j^{\prime }}$ 。

为了方便叙述，我们将图G的顶点按行和列进行分层，其中$\left(u_1,v_i\right),\left(u_2,v_i\right),\cdots ,\left(u_n,v_i\right)$ 为第i行的点，而$\left(u_j,v_1\right),\left(u_j,v_2\right),\cdots ,\left(u_j,v_n\right)$ 为第j列的点。因此对于任意图G中的点$\left(u_i,v_j\right)$ ，我们称其位于第j行第i列。

我们之所以采用这种线性的排序方式，是因为对于乘积图最自然的排序方法是依次按照行或者列进行排序，在本文中我们采取按照列依次进行排序，对于同一列的点我们按照行依次进行排序。

对于任意$\left(u_i,v_j\right)\in V\left(G\right)$ ，由直积图的性质以及弱k-可达的定义可知，从点$\left(u_i,v_j\right)$ 弱k-可达的顶点可以在图G的任何行，因此我们分别来看每一行可达的顶点数量。对于第j行，由于$\left(u_i,v_j\right)$ 只能通过其他行再到第j行，因此对于弱k-可达且在第j行的顶点最多为$\lfloor k/2\rfloor$ 。对于除了第j行以外的每一行，从点$\left(u_i,v_j\right)$ 弱k-可达的顶点最多为$\lceil k/2\rceil$ 。加上点$(u_i,v_j)$ 本身，就有$wco{l}_k\left(G\right)\le \lfloor k/2\rfloor +\left(m-1\right)\lceil k/2\rceil +1$ 。

对于从顶点$\left(u_i,v_j\right)$ 强k-可达的顶点，对于不同的k有不同的结果。当$k=1$ 时，点$\left(u_i,v_j\right)$ 只能够到达除了点$\left(u_i,v_{j-1}\right)$ 以外的所有第$i-1$ 列的点，故$co{l}_k\left(G\right)\le m-1+1=m$ .当$k=2$ 时，点$\left(u_i,v_j\right)$ 可额外通过第$i+1$ 列中的顶点到达第i列第$t\left(1\le t\le j-1\right)$ 行的顶点，故$co{l}_k\left(G\right)\le m+j-1$ 。当j取最大值时候，就有$co{l}_k\left(G\right)\le m+m-1=2m-1$ .当$k\ge 3$ 时，点$\left(u_i,v_j\right)$ 可额外到达点$\left(u_i,v_{j-1}\right)$ ，故$co{l}_k\left(G\right)\le 2m$ 。

定理6 对于所有的整数$k>0$ ，如果图$G=P_n\square K_m$ ，其中$P_n$ 为一条长为n的路，$K_m$ 为m个顶点的完全图，则$wco{l}_k\left(G\right)\le mk+1$ ，$co{l}_k\left(G\right)\le m+1$ 。

证明 对于路$P_n$ ，我们用$\sigma$ 来记作它的一个线性序$\left(u_1,u_2,\cdots ,u_n\right)$ ，对于完全图$K_m$ ，我们用$\phi$ 来记作它的一个线性序$\left(v_1,v_2,\cdots ,v_m\right)$ ，对于图$G=P_n\times K_m$ 的顶点集$V\left(G\right)=\left(\left(u_1,v_1\right),\left(u_1,v_2\right),\cdots ,\left(u_1,v_m\right),\left(u_2,v_1\right),\cdots ,\left(u_2,v_m\right),\cdots ,\left(u_n,v_1\right),\cdots ,\left(u_n,v_m\right)\right)$ 。令L为图G的一个线性序，由于笛卡尔积与直积有相同的顶点集合，我们直接采用与直积相同的顶点排序规则。

我们先来看对于图G的弱k-染色数上界。对于图G中的任何一个顶点$\left(u_i,v_j\right)$ ，从点$\left(u_i,v_j\right)$ 弱k-可达的顶点可以在图G的任何行，因此我们分别来看每一行可达的顶点数量。对于第j行，显然最多有k个顶点。对于不同于第j行的任何一行，顶点$\left(u_i,v_j\right)$ 可以到达第i列的任何行的顶点，因此每行最多也有k个顶点，加上顶点$\left(u_i,v_j\right)$ 本身，故有$wco{l}_k\left(G\right)\le mk+1$ 。

下面我们考虑图G的强k-染色数上界。对于图G中的任何一个顶点$\left(u_i,v_j\right)$ ，从点$\left(u_i,v_j\right)$ 强k-可达的顶点只能在图G的第i列与第$i-1$ 列，我们对不同的k进行讨论。当$k=1$ 时，点$\left(u_i,v_j\right)$ 只能到达第i列第t层$\left(1\le t\le j-1\right)$ 的点以及点$\left(u_{i-1},v_j\right)$ 加上点$\left(u_i,v_j\right)$ 本身，因此$co{l}_k\left(G\right)\le 1+j-1+1=j+1$ 。当j取最大时，$co{l}_k\left(G\right)\le m+1$ 。当$k\ge 2$ 时，点$\left(u_i,v_j\right)$ 可额外到达第$i-1$ 列第t层$\left(j+1\le t\le m\right)$ 的点。因此，$co{l}_k\left(G\right)\le m+1$ 。

定理7 对于所有的整数$k>0$ ，如果图$G=P_n$ $⊠$ $K_m$ ，其中$P_n$ 为一条长为n的路，$K_m$ 为m个顶点的完全图，则$wco{l}_k\left(G\right)\le m\left(k+1\right)$ ，$co{l}_k\left(G\right)\le 2m$ 。

证明 对于路$P_n$ ，我们用$\sigma$ 来记作它的一个线性序$\left(u_1,u_2,\cdots ,u_n\right)$ ，对于完全图$K_m$ ，我们用$\phi$ 来记作它的一个线性序$\left(v_1,v_2,\cdots ,v_m\right)$ ，对于图$G=P_n\times K_m$ 的顶点集$V\left(G\right)=\left(\left(u_1,v_1\right),\left(u_1,v_2\right),\cdots ,\left(u_1,v_m\right),\left(u_2,v_1\right),\cdots ,\left(u_2,v_m\right),\cdots ,\left(u_n,v_1\right),\cdots ,\left(u_n,v_m\right)\right)$ 。令L为图G的一个线性序，由于强积与直积有相同的顶点集合，我们直接采用与直积相同的顶点排序规则。

我们首先考虑对于图G的弱k-染色数上界。对于图G中的任何一个顶点$\left(u_i,v_j\right)$ ，从点$\left(u_i,v_j\right)$ 弱k-可达的顶点可以在图G的任何行，故我们分别计算每一行可达的顶点数。对于第j行，从点$\left(u_i,v_j\right)$ 弱k-可达的顶点至多为k个。而对于除了第j行之外的任何一行，从点$\left(u_i,v_j\right)$ 弱k-可达的顶点至多为$k+1$ 个，再加上顶点$\left(u_i,v_j\right)$ 本身，因此有$wco{l}_k\left(G\right)\le m\left(k+1\right)$ 。

下面来考虑图G的强k-染色数上界。我们仍考虑不同的k。对于$k=1$ ，顶点$\left(u_i,v_j\right)$ 可到达第$i-1$ 行的所有顶点，以及第i列第t行$\left(1\le t\le j-1\right)$ 的顶点。加上顶点$\left(u_i,v_j\right)$ 本身，则有$co{l}_k\left(G\right)\le m+j$ 。当j取最大值时，$co{l}_k\left(G\right)\le 2m$ 。对于$k\ge 2$ 时，顶点$\left(u_i,v_j\right)$ 可额外到达第i列第t行$\left(j+1\le t\le m\right)$ 的顶点，因此有$co{l}_k\left(G\right)\le 2m$ 。

3. 结语

目前对于图的广义染色数的研究成果十分丰富，但是对于乘积图的广义染色数的研究较少，本文以特定的图类，即路与完全图的三种乘积图为研究对象，分别给出了他们在指定线性序下的广义染色数线性的上界。由于广义染色数上界与我们给定的线性序有关，而本文仅采取了对于乘积图最为常见的一种线性序。那么对于路与完全图的乘积结构在其他线性序下是否能有更好的广义染色数上界，值得我们研究。更为一般性地，如果将本文中的特定图类推广，即对于任意两个给定图的乘积图的广义染色数计算复杂度是多少以及能否给出一般的公式更是待研究的问题。