浙江师范大学数学与计算机科学学院，浙江 金华

收稿日期：2021年8月6日；录用日期：2021年8月31日；发布日期：2021年9月8日

摘要

图G的一个正常全染色是指一个映射 $\phi :V\left(G\right)\cup E\left(G\right)\to N$，使得 $V\left(G\right)\cup E\left(G\right)$ 中任意两个相邻的或相关联的元素染不同颜色。一个t-区间是指t个连续整数组成的集合。如果G的一个使用了颜色 $1,2,\cdots ,t$ 的全染色使得G中任意顶点v以及与v关联的边使用了 $d_G\left(v\right)+1$ 种连续的颜色，其中 $d_G\left(v\right)$ 是G中顶点v的度，并且G中至少存在一个顶点或者一条边被染颜色i， $i=1,2,\cdots ,t$，则称此全染色为图G的一个区间全染色。在本文中，我们研究外平面图的区间全染色。

关键词

区间全染色，外平面图

The Interval Total Colorings of Outerplane Graphs

Qiaohui Zhang, Puning Jing

College of Mathematics and Computer Science, Zhejiang Normal University, Jinhua Zhejiang

Received: Aug. 6^th, 2021; accepted: Aug. 31^st, 2021; published: Sep. 8^th, 2021

ABSTRACT

A total coloring of a graph G is a mapping $\phi :V\left(G\right)\cup E\left(G\right)\to N$, such that no adjacent vertices, edges, and no incidnet vertices and edges in $V\left(G\right)\cup E\left(G\right)$ obtain the same color. A t-interval is a set of t consecutive integers. An interval total t-coloring of a graph G is a total coloring of G with colors $1,2,\cdots ,t$ such that at least one vertex or edge of G is colored by i, $i=1,2,\cdots ,t$, and the edges incident to each vertex v together with v are colored by $d_G\left(v\right)+1$ consecutive colors, where $d_G\left(v\right)$ is the degree of the vertex v in G. In this paper, we study the interval total coloring of outerplane graphs.

Keywords:Interval Total Coloring, Outerplane Graphs

Copyright © 2021 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是一个点集为 $V\left(G\right)$，边集为 $E\left(G\right)$ 的图，它的最大度，最小度分别为 $\Delta \left(G\right)$，$\delta \left(G\right)$。对于任意顶点 $v\in V\left(G\right)$，令 $d_G\left(v\right)$ 为G中顶点 的度。对于G的一个全染色 $\phi$，将 $S\left[v,\phi \right]$ 定义为

$S\left[v,\phi \right]=\left\{\phi \left(v\right)\right\}\cup \left\{\phi \left(e\right)|e关联于顶点v\right\}$。

对于任意两个整数 $a,b$，$\left[a,b\right]=\left\{a,a+1,\cdots ,b\right\}$。一个t-区间是指t个连续整数组成的集合。设 $\phi$ 为G的一个全染色，所使用的颜色集合为 $C=\left\{1,2,\cdots ,t\right\}$，且每种颜色至少出现一次，若对于每一个顶点 $v\in V\left(G\right)$，与v相关联的边以及v本身所使用的颜色构成一个整数区间，则称此全染色为图G的一个t-区间全染色。我们将使得图G存在一个t-区间全染色的最小的和最大的非负整数t分别称为图G的最小区间全色数和最大区间全色数，分别记为 $w_t\left(G\right)$ 和 $W_t\left(G\right)$。

2005年，Petrosyan在 [1] 中首先给出了图的区间全染色的概念，并且证明了如果 $m+n+2-\gcd \left(m,n\right)\le t\le m+n+1$，那么完全二部图 $K_{m,n}$ 存在t-区间全染色。2008年，Petrosyan和Torosyan在 [2] 中得出了 $w_t\left(K_n\right),W_t\left(K_n\right)$ 和 $w_t\left(Q_n\right)$ 的值以及 $W_t\left(Q_n\right)$ 的下界。2009年，Petrosyan和Torosyan在 [3] 中得出了 $W_t\left(K_{m,n}\right)$ 的值。2009年，Petrosyan，Shashikyan和Khachatryan在 [4] [5] 中得出了树的最小区间全色数的上界以及轮图 $W_n$ 的 $w_t\left(W_n\right)$ 和 $W_t\left(W_n\right)$ 的值。2010年，Petrosyan，Shashikyan和Torosyan在 [6] 中得出了 $\left(r,r-1\right)$ -双正则二部图以及 $\left(r,2\right)$ -双正则二部图都存在区间全染色。2013年，Petrosyan和Khachatryan在 [7] 中证明了路或圈与r-正则图的笛卡尔积分别存在区间全染色。2014年，Petrosyan和Khachatryan在 [8] 中得出了 $w_t\left(K_{n,\cdots ,n}\right)$ 的上界和 $W_t\left(K_{n,\cdots ,n}\right)$ 的下界。

2. 主要结果

在展示主要结果前，我们先建立一些引理。

引理1 [9] 如果图G是一个 $\text{Δ}=3$ 的2-连通外平面图，则至少有以下之一成立：

(1) 存在相邻的两个2度点u和v；

(2) 存在一个三角面uvw使得 $d_G\left(u\right)=d_G\left(w\right)=3$，$d_G\left(v\right)=2$。

定理1 如果图G是一个 $\text{Δ}=3$ 的外平面图，则 $w_t\left(G\right)\le 5$。

证明：我们先考虑 $\delta =2$ 的情况。

情况1 G中不存在割边。

我们对图G的顶点数 $\left|V\left(G\right)\right|$ 进行归纳。对于 $\left|V\left(G\right)\right|=4$，结论显然成立。假设此定理对于图H成立，其中 $\Delta \left(H\right)=3$，$\delta \left(H\right)=2$ 且 $4<\left|V\left(H\right)\right|<\left|V\left(G\right)\right|$。由引理1知：至少有以下之一成立：(1) 存在相邻的两个2度点u和v；(2) 存在一个三角面 使得 $d_G\left(u\right)=d_G\left(w\right)=3$，$d_G\left(v\right)=2$。因此，我们考虑两种子情况。

情况1.1 $uv\in E\left(G\right)$ 且 $d_G\left(u\right)=d_G\left(v\right)=2$。

显然，此时G中存在两个不同顶点x，y使得 $ux\in E\left(G\right)$，$vy\in E\left(G\right)$。

情况1.1.1 $xy\notin E\left(G\right)$。

令 $H=G-u-v+xy$，显然， $\left|V\left(H\right)\right|<\left|V\left(G\right)\right|$，且 $\Delta \left(H\right)=3$，$\delta \left(H\right)=2$。由归纳假设知：H存在一个区间全染色 $\phi$ 且 $w_t\left(H\right)\le 5$。

(1) $d_G\left(x\right)=d_G\left(y\right)=2$，即 $d_H\left(x\right)=d_H\left(y\right)=2$。

① $\phi \left(xy\right)=1\left(或5\right)$。

不失一般性，根据对称性可假设 $\phi \left(x\right)=2\left(3\right)$，$\phi \left(y\right)=3\left(4\right)$。将边xy删掉，然后分别将边xu，vy和uv染颜色4(2)，1(5)，3(3)。然后将顶点u和v分别染颜色1(5)和2(4)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

② $\phi \left(xy\right)=2\left(或4\right)$。

此时，将边xy删掉，然后分别将边xu，vy和uv染颜色2(4)，2(4)，3(3)。因为 $\phi \left(x\right)\ne \phi \left(y\right)$，所以如果 $\phi \left(x\right)=4\left(5\right)$ 或 $\phi \left(y\right)=1\left(2\right)$，那么将顶点u和v分别染颜色1(2)和4(5)。否则将顶点u和v分别染颜色4(5)和1(2)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

③ $\phi \left(xy\right)=3$。

此时，将边xy删掉，然后分别将边xu，vy和uv染颜色3，3，4。因为 $\phi \left(x\right)\ne \phi \left(y\right)$，所以如果 $\phi \left(x\right)=5$ 或 $\phi \left(y\right)=2$，那么将顶点u和v分别染颜色2和5。否则将顶点u和v分别染颜色5和2。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(2) $d_G\left(x\right)=2$ 且 $d_G\left(y\right)=3$。

① $\phi \left(xy\right)=a$，$a=1,2,3,4$。

在这些情况中，染色规则与(1)中对应相同。

② $\phi \left(xy\right)=5$。

如果 $\phi \left(x\right)=4$ 或 $\phi \left(y\right)=2$，那么将边xy删掉，然后分别将边xu，vy和uv染颜色2，5，3，将顶点u和v分别染颜色1和4。否则就将边xy删掉，然后分别将边xu，vy和uv染颜色5，1，3，将顶点u和v分别染颜色4和2。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(3) $d_G\left(x\right)=d_G\left(y\right)=3$。

① $\phi \left(xy\right)=1\left(或5\right)$。

如果 $\phi \left(x\right)=4$ 或 $\phi \left(y\right)=2$，那么将边xy删掉，然后分别将边xu，vy和uv染颜色1，5，3，将顶点u和v分别染颜色2和4。否则就将边xy删掉，然后分别将边xu，vy和uv染颜色5，1，3，将顶点u和v分别染颜色4和2。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

② $\phi \left(xy\right)=a$，$a=2,3,4$。

在这些情况中，染色规则与(1)中对应相同。

情况1.1.2 $xy\in E\left(G\right)$。

令 $H=G-u-v$，显然， $\left|V\left(H\right)\right|<\left|V\left(G\right)\right|$ 且 $\Delta \left(H\right)=3$，由归纳假设知：H存在一个5-区间全染色 $\phi$。显然此时有： $d_G\left(x\right)=d_G\left(y\right)=3$。

① $\phi \left(xy\right)=1\left(或5\right)$。

不失一般性，根据对称性可假设 $\phi \left(x\right)=2\left(3\right)$，$\phi \left(y\right)=3\left(4\right)$。然后分别将边xu，vy和uv染颜色4(2)，4(2)，3(3)。然后将顶点u和v分别染颜色5(4)和2(1)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

② $\phi \left(xy\right)=2\left(或4\right)$。

(i) $S\left[x,\phi \right]=S\left[y,\phi \right]=\left[1,3\right]\left(或\left[3,5\right]\right)$。

不失一般性，根据对称性可假设 $\phi \left(x\right)=3\left(5\right)$，$\phi \left(y\right)=1\left(3\right)$。然后分别将边xu，vy和uv染颜色4(2)，4(2)，3(3)。然后将顶点u和v分别染颜色2(1)和5(4)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(ii) $S\left[x,\phi \right]=\left[1,3\right]$，$S\left[y,\phi \right]=\left[2,4\right]$ $\left(或S\left[x,\phi \right]=\left[2,4\right],S\left[y,\phi \right]=\left[3,5\right]\right)$。

因为 $4\left(5\right)\notin S\left[x,\phi \right]$ 且 $1\left(2\right)\notin S\left[y,\phi \right]$，所以可以分别将边xu，vy和uv染颜色4(5)，1(2)，3(3)。然后将顶点u和v分别染颜色5(4)和2(1)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(iii) $S\left[x,\phi \right]=S\left[y,\phi \right]=\left[2,4\right]\left(或\left[2,4\right]\right)$。

不失一般性，根据对称性可假设 $\phi \left(x\right)=3\left(2\right)$，$\phi \left(y\right)=4\left(3\right)$。这两种子情况可以用相同的染色方法。因为 $5\notin S\left[x,\phi \right]$ 且 $1\notin S\left[y,\phi \right]$，所以分别将边xu，vy和uv染颜色5，1，3。然后将顶点u和v分别染颜色4和2。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

③ $\phi \left(xy\right)=3$。

(i) $S\left[x,\phi \right]=S\left[y,\phi \right]=\left[1,3\right]$。

不失一般性，根据对称性可假设 $\phi \left(x\right)=1$，$\phi \left(y\right)=2$。这种情况下，染色规则与情况1.1.2中②(i)的对应情况一样。

(ii) $S\left[x,\phi \right]=\left[1,3\right]$，$S\left[y,\phi \right]=\left[2,4\right]$。

如果 $\phi \left(x\right)\ne 1$ 且 $\phi \left(y\right)\ne 2$，染色规则与情况1.1.2中②(ⅱ)的对应情况一样。否则就分别将边xu，vy和uv染颜色4，5，3。然后将顶点u和v分别染颜色2和4。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(iii) $S\left[x,\phi \right]=\left[1,3\right]$，$S\left[y,\phi \right]=\left[3,5\right]$。

因为 $4,5\notin S\left[x,\phi \right]$ 且 $1,2\notin S\left[y,\phi \right]$，所以分别将边xu，vy和uv染颜色4，2，3。然后将顶点u和v分别染颜色5和1。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(iv) $S\left[x,\phi \right]=S\left[y,\phi \right]=\left[2,4\right]\left(或\left[3,5\right]\right)$。

不失一般性，根据对称性可假设 $\phi \left(x\right)=2\left(4\right)$，$\phi \left(y\right)=4\left(5\right)$。染色规则与情况1.1.2中②的对应情况一样。

(v) $S\left[x,\phi \right]=\left[2,4\right]$，$S\left[y,\phi \right]=\left[3,5\right]$。

如果 $\phi \left(x\right)\ne 4$ 且 $\phi \left(y\right)\ne 5$，那么将边xy删掉，然后分别将边xu，vy和uv染颜色5，2，3，将顶点u和v分别染颜色4和1。否则就将边xy删掉，然后分别将边xu，vy和uv染颜色1，2，3，将顶点u和v分别染颜色2和1。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

情况1.2 $uv,vw,uw\in E\left(G\right)$，且 $d_G\left(u\right)=d_G\left(w\right)=3$，$d_G\left(v\right)=2$。

令 $H=G-v$，显然， $\left|V\left(H\right)\right|<\left|V\left(G\right)\right|$ 且 $\Delta \left(H\right)=3$，由归纳假设知：H存在一个5-区间全染色 $\phi$。我们考虑边uw的颜色 $\phi \left(uw\right)$。由于 $d_G\left(u\right)=3$，所以G中存在一个顶点 $u^{\prime }\in N_G\left(u\right)\backslash \left\{v,w\right\}$。同理存在一个顶点 $w^{\prime }\in N_G\left(w\right)\backslash \left\{u,v\right\}$。

情况1.2.1 $\phi \left(uw\right)=1\left(或5\right)$。

不失一般性，根据对称性可假设 $\phi \left(u\right)=3\left(3\right)$，$\phi \left(w\right)=2\left(4\right)$。如果 $\phi \left(u^{\prime }\right)\ne 4\left(2\right)$，那么将顶点u的颜色改为颜色4(2)，然后将边uv，vw和顶点v分别染颜色3(3)，4(2)，5(1)。否则就将顶点u和边uw的颜色改为颜色5(1)和4(2)，然后将边uv，vw和顶点v分别染颜色3(3)，5(1)，4(2)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

情况1.2.2 $\phi \left(uw\right)=2\left(或4\right)$。

(1) $S\left[u,\phi \right]=S\left[w,\phi \right]=\left[1,3\right]\left(或\left[3,5\right]\right)$。

不失一般性，根据对称性可假设 $\phi \left(u\right)=1\left(3\right)$，$\phi \left(w\right)=3\left(5\right)$。如果 $\phi \left(w^{\prime }\right)\ne 4\left(\phi \left(u^{\prime }\right)\ne 2\right)$，那么将顶点w (u)的颜色改为颜色4(2)，然后将边uv，vw和顶点v分别染颜色4(3)，3(2)，2(4)。否则就将顶点w(u)和边uw的颜色分别改为颜色2(4)和4(2)，然后将边uv，vw和顶点v分别染颜色2(3)，3(4)，4(2)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(2) $S\left[u,\phi \right]=\left[1,3\right]$，$S\left[w,\phi \right]=\left[2,4\right]$ $\left(S\left[u,\phi \right]=\left[2,4\right],S\left[w,\phi \right]=\left[3,5\right]\right)$。

① $\phi \left(u\right)=1\left(3\right)$ 且 $\phi \left(w\right)=3\left(5\right)$。

如果 $\phi \left(w^{\prime }\right)\ne 5\left(\phi \left(u^{\prime }\right)\ne 1\right)$，那么将顶点w (u)的颜色改为颜色5 (1)，然后将边uv，vw和顶点v分别染颜色4(3)，3(2)，2(4)。如果 $\phi \left(w^{\prime }\right)=5$ 且 $\phi \left(u^{\prime }\right)\ne 4$ $\left(\phi \left(u^{\prime }\right)=1且\phi \left(w^{\prime }\right)\ne 2\right)$，那么将顶点u，w和边uw的颜色分别改为颜色4(4)，2(2)和1(5)，然后将边uv，vw和顶点v分别染颜色2(3)，3(4)，1(5)。如果 $\phi \left(w^{\prime }\right)=5$ 且 $\phi \left(u^{\prime }\right)=4$ $\left(\phi \left(u^{\prime }\right)=1且\phi \left(w^{\prime }\right)=2\right)$，那么将顶点u和w的颜色分别改为颜色5(5)和1(1)，然后将边uv，vw和顶点v分别染颜色4(3)，3(2)，2(4)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

② $\phi \left(u\right)=1\left(2\right)$ 且 $\phi \left(w\right)=4\left(5\right)$。

因为 $4\left(1\right)\notin S\left[u,\phi \right]$ 且 $5\left(2\right)\notin S\left[w,\phi \right]$，所以将边uv，vw和顶点v分别染颜色4(1)，5(2)，3(3)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

③ $\phi \left(u\right)=3\left(2\right)$ 且 $\phi \left(w\right)=4\left(3\right)$。

如果 $\phi \left(u^{\prime }\right)\ne 4$ 且 $\phi \left(w^{\prime }\right)\ne 5$ $\left(\phi \left(u^{\prime }\right)\ne 1且\phi \left(w^{\prime }\right)\ne 2\right)$，那么将顶点u和w的颜色分别改为颜色4(1)，5(2)，然后将边uv，vw和顶点v分别染颜色3(2)，4(3)，2(4)。如果 $\phi \left(u^{\prime }\right)=4$ 且 $\phi \left(w^{\prime }\right)\ne 5$ $\left(\phi \left(u^{\prime }\right)\ne 1且\phi \left(w^{\prime }\right)=2\right)$，那么将顶点u，w和边uw的颜色分别改为颜色2(1)，5(4)和4(2)，然后将边uv，vw和顶点v分别染颜色3(4)，2(3)，4(2)。如果 $\phi \left(u^{\prime }\right)\ne 4$ 且 $\phi \left(w^{\prime }\right)=5$ $\left(\phi \left(u^{\prime }\right)=1且\phi \left(w^{\prime }\right)\ne 2\right)$，那么将顶点u和w的颜色分别改为颜色4(5)，1(2)，然后将边uv，vw和顶点v分别染颜色3(2)，4(3)，2(4)。如果 $\phi \left(u^{\prime }\right)=4$ 且 $\phi \left(w^{\prime }\right)=5$ $\left(\phi \left(u^{\prime }\right)=1且\phi \left(w^{\prime }\right)=2\right)$，那么将顶点u，w和边uw的颜色分别改为颜色2(5)，1(4)和4(2)，然后将边uv，vw和顶点v分别染颜色3(4)，2(3)，4(2)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(3) $S\left[u,\phi \right]=S\left[w,\phi \right]=\left[2,4\right]\left(\left[2,4\right]\right)$。

不失一般性，根据对称性可假设 $\phi \left(u\right)=3\left(2\right)$，$\phi \left(w\right)=4\left(3\right)$。如果 $\phi \left(u^{\prime }\right)\ne 1\left(\phi \left(w^{\prime }\right)\ne 5\right)$，那么将顶点u (w)的颜色改为颜色1(5)，然后将边uv，vw和顶点v分别染颜色3(5)，1(3)，2(4)。否则就将顶点u (w)的颜色改为颜色5(1)，然后将边uv，vw和顶点v分别染颜色3(5)，1(3)，2(4)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

情况1.2.3 $\phi \left(uw\right)=3$。

(1) $S\left[u,\phi \right]=S\left[w,\phi \right]=\left[1,3\right]$。

不失一般性，根据对称性可假设 $\phi \left(u\right)=1$，$\phi \left(w\right)=2$。如果 $\phi \left(w^{\prime }\right)\ne 4$，那么将顶点w的颜色改为颜色4，然后将边uv，vw和顶点v分别染颜色4，2，3。否则就将顶点w和边uw的颜色分别改为3，4，然后将边uv，vw和顶点v分别染颜色3，2，4。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(2) $S\left[u,\phi \right]=\left[1,3\right]$，$S\left[w,\phi \right]=\left[2,4\right]$ $\left(S\left[u,\phi \right]=\left[1,3\right],S\left[w,\phi \right]=\left[3,5\right]\right)$。

因为 $4\left(4\right)\notin S\left[u,\phi \right]$ 且 $5\left(2\right)\notin S\left[w,\phi \right]$，所以将边uv，vw和顶点v分别染颜色4(4)，5(2)，3(3)。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(3) $S\left[u,\phi \right]=S\left[w,\phi \right]=\left[2,4\right]$。

不失一般性，根据对称性可假设 $\phi \left(u\right)=2$，$\phi \left(w\right)=4$。如果 $\phi \left(u^{\prime }\right)\ne 5$，那么将顶点u的颜色改为颜色5，然后将边uv，vw和顶点v分别染颜色2，1，3。否则就将顶点u的颜色改为颜色1，然后将边uv，vw和顶点v分别染颜色2，1，3。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(4) $S\left[u,\phi \right]=\left[2,4\right]$，$S\left[w,\phi \right]=\left[3,5\right]$

因为 $1\notin S\left[u,\phi \right]$ 且 $2\notin S\left[w,\phi \right]$，所以将边uv，vw和顶点v分别染颜色1，2，3。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

(5) $S\left[u,\phi \right]=S\left[w,\phi \right]=\left[3,5\right]$。

不失一般性，根据对称性可假设 $\phi \left(u\right)=4$，$\phi \left(w\right)=5$。如果 $\phi \left(w^{\prime }\right)\ne 2$，那么将顶点w的颜色改为颜色2，然后将边uv，vw和顶点v分别染颜色2，1，3。否则就将顶点w和边vw的颜色分别改为3，2，然后将边uv，vw和顶点v分别染颜色3，1，2。剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所获得的全染色是G的一个5-区间全染色。

情况2 G中存在割边。

显然，G中存在某条割边与一个2-连通块B关联。

情况2.1 $\left|V\left(B\right)\right|\ge 5$。

此时，我们可以在块B中借助数学归纳法证明此定理，方法情况1与一样。

情况2.2 $\left|V\left(B\right)\right|=3$。

令顶点w是块B与割边的公共顶点。显然 $d_G\left(w\right)=3$。令 $N_B\left(w\right)=\left\{u,v\right\}$，令x为距离顶点w最近的3度点。我们先假设x不在圈上。

情况2.2.1x与顶点w相邻。

对 $\left|V\left(G\right)\right|$ 进行归纳。如果 $\left|V\left(G\right)\right|=7$，定理成立。假设此定理对于图H成立，其中 $\Delta \left(H\right)=3$，$\delta \left(H\right)=2$ 且 $7<\left|V\left(H\right)\right|<\left|V\left(G\right)\right|$。令 $H=G-u-v-w$。显然， $\left|V\left(H\right)\right|<\left|V\left(G\right)\right|$ 且 $\Delta \left(H\right)=3$，$\delta \left(H\right)=2$。由归纳假设知：H存在一个5-区间全染色 $\phi$。令 $\phi \left(xw\right)=a$。

(1) $\phi \left(xw\right)=a\in \left\{1,5\right\}$。

如果 $\phi \left(x\right)\ne 2$，那么将顶点u，v和w分别染颜色4，3，2，然后将边uw，vw和uv分别染颜色3，4，2。否则就将顶点u，v和w分别染颜色4，2，3，然后将边uw，vw和uv分别染颜色2，4，3。

(2) $\phi \left(xw\right)=a\in \left\{2,3,4\right\}$。

存在两个正整数b，c使得 $\left\{1,a,b,c\right\}=\left[1,4\right]$，其中 $a\ne b\ne c\ne 1$ 且 $a,b,c\in \left\{2,3,4\right\}$。如果 $\phi \left(x\right)\ne 1$，那么将顶点u，v和w分别染颜色c，b，1，然后将边uw，vw和uv分别染颜色b，c，a。如果 $\phi \left(x\right)=1$ 且 $\phi \left(xw\right)=2$，那么将顶点u，v和w分别染颜色3，1，4，然后将边uw，vw和uv分别染颜色1，3，2。如果 $\phi \left(x\right)=1$ 且 $\phi \left(xw\right)\in \left\{3,4\right\}$，那么将顶点u，v和w分别染颜色2，1，4，然后将边uw，vw和uv分别染颜色1，2，3。

情况2.2.2顶点x与顶点w之间是一条路 $P_m$。令 $V\left(P_m\right)=\left\{x_1,x_2,\cdots ,x_m\right\}$，其中 $x_1=x$，$x_m=w$。

1. $\phi \left(x_1{x}_2\right)=1$。

给图G定义一个全染色 $\psi$ ：

(1) 对于任意 $i\in \left\{2,3,\cdots ,m-1\right\}$，

$\psi \left(x_i\right)=\{\begin{array}{cc}2& i\equiv 2\left(\mathrm{mod}3\right)\\ 1& i\equiv 0\left(\mathrm{mod}3\right)\\ 3& i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

(2) 对于任意 $j\in \left\{1,2,\cdots ,m-1\right\}$，

$\psi \left(x_j{x}_{j+1}\right)=\{\begin{array}{cc}1& j\equiv 1\left(\mathrm{mod}3\right)\\ 3& j\equiv 2\left(\mathrm{mod}3\right)\\ 2& j\equiv 0\left(\mathrm{mod}3\right)\end{array}$

如果 $\phi \left(x_1\right)=2$，那么交换(1)中染颜色2和3的顶点的颜色，且同时交换(2)中染颜色2和3的边的颜色。显然 $\psi \left(x_{m-1}{x}_m\right)=1$ 或2或3。

① $\psi \left(x_{m-1}{x}_m\right)=1$。

如果 $\psi \left(x_{m-1}\right)=2$，那么将顶点u，v和w分别染颜色4，2，3，然后将边uw，vw和uv分别染颜色2，4，3。如果 $\psi \left(x_{m-1}\right)=3$，那么将顶点u，v和w分别染颜色4，3，2，然后将边uw，vw和uv分别染颜色3，4，2。

② $\psi \left(x_{m-1}{x}_m\right)=2\left(3\right)$。

因为 $\psi \left(x_{m-1}\right)\ne 4$，所以将顶点u，v和w分别染颜色3(2)，1(1)，4(4)，然后将边uw，vw和uv分别染颜色1(1)，3(2)，2(3)。

2. $\phi \left(x_1{x}_2\right)=2\left(3\right)$。

在1中的(1)和(2)的基础上，交换(1)中染颜色1(1)和2(3)的顶点的颜色，且同时交换(2)中染颜色1(1)和2(3)的边的颜色。假设新得到的全染色为 ${\psi }_1\left({\psi }_2\right)$。如果 $\phi \left(x_1\right)=1\left(2\right)$，那么在 ${\psi }_1\left({\psi }_2\right)$ 的基础上，交换(1)中染颜色1(1)和3(2)的顶点的颜色，且同时交换(2)中染颜色1(1)和3(2)的边的颜色。显然 ${\psi }_1\left(x_{m-1}{x}_m\right)=1$ 或2或3 $\left({\psi }_2\left(x_{m-1}{x}_m\right)=1,2,3\right)$。在各种子情况下，染色规则与1中①②③分别对应相同。

3. $\phi \left(x_1{x}_2\right)=4$。

给图G定义一个全染色 ${\psi }^{\prime }$ ：

(1) 对于任意 $i\in \left\{2,3,\cdots ,m-1\right\}$，

${\psi }^{\prime }\left(x_i\right)=\{\begin{array}{cc}2& i\equiv 2\left(\mathrm{mod}3\right)\\ 4& i\equiv 0\left(\mathrm{mod}3\right)\\ 3& i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

(2) 对于任意 $j\in \left\{1,2,\cdots ,m-1\right\}$，

${\psi }^{\prime }\left(x_j{x}_{j+1}\right)=\{\begin{array}{cc}4& j\equiv 1\left(\mathrm{mod}3\right)\\ 3& j\equiv 2\left(\mathrm{mod}3\right)\\ 2& j\equiv 0\left(\mathrm{mod}3\right)\end{array}$

如果 $\phi \left(x_1\right)=2$，那么交换(1)中染颜色2和3的顶点的颜色，且同时交换(2)中染颜色2和3的边的颜色。显然 ${\psi }^{\prime }\left(x_{m-1}{x}_m\right)=2$ 或3或4。

① ${\psi }^{\prime }\left(x_{m-1}{x}_m\right)=2$ 或3。

因为 ${\psi }^{\prime }\left(x_{m-1}\right)\ne 1$，所以将顶点u，v和w分别染颜色4，3，1，然后将边uw，vw和uv分别染颜色3，4，2。

② ${\psi }^{\prime }\left(x_{m-1}{x}_m\right)=4$。

因为 ${\psi }^{\prime }\left(x_{m-1}\right)\ne 1$，所以将顶点u，v和w分别染颜色3，2，1，然后将边uw，vw和uv分别染颜色2，3，4。

4. $\phi \left(x_1{x}_2\right)=5$。

给图G定义一个全染色 ${\psi }^{″}$ ：

(1) 对于任意 $i\in \left\{2,3,\cdots ,m-1\right\}$，

${\psi }^{″}\left(x_i\right)=\{\begin{array}{cc}3& i\equiv 2\left(\mathrm{mod}3\right)\\ 5& i\equiv 0\left(\mathrm{mod}3\right)\\ 4& i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

(2) 对于任意 $j\in \left\{1,2,\cdots ,m-1\right\}$，

${\psi }^{″}\left(x_j{x}_{j+1}\right)=\{\begin{array}{cc}5& j\equiv 1\left(\mathrm{mod}3\right)\\ 4& j\equiv 2\left(\mathrm{mod}3\right)\\ 3& j\equiv 0\left(\mathrm{mod}3\right)\end{array}$

如果 $\phi \left(x_1\right)=3$，那么交换(1)中染颜色3和4的顶点的颜色，且同时交换(2)中染颜色3和4的边的颜色。显然 ${\psi }^{″}\left(x_{m-1}{x}_m\right)=3$ 或4或5。

① ${\psi }^{″}\left(x_{m-1}{x}_m\right)=3\left(4\right)$。

因为 ${\psi }^{″}\left(x_{m-1}\right)\ne 1$，所以将顶点u，v和w分别染颜色4(3)，2(2)，1(1)，然后将边uw，vw和uv分别染颜色2(2)，4(3)，3(4)。

② ${\psi }^{″}\left(x_{m-1}{x}_m\right)=5$。

因为 ${\psi }^{″}\left(x_{m-1}\right)\ne 2$，所以将顶点u，v和w分别染颜色4，3，2，然后将边uw，vw和uv分别染颜色3，4，2。

最后，我们考虑顶点x在圈上。令此圈为 $C_t$ 且 $V\left(C_t\right)=\left\{x_1,x_2,\cdots ,x_t\right\}$，其中 $x_1=x$。

情况2.2.3x与顶点w相邻。我们先染此圈。

1. $t=3k$，$k\in N$。

给图 $C_t$ 定义一个全染色 $\psi$ :

(1) 对于任意 $i\in \left\{1,2,\cdots ,t\right\}$，

$\psi \left(x_i\right)=\{\begin{array}{cc}2& i\equiv 0\left(\mathrm{mod}3\right)\\ 1& i\equiv 1\left(\mathrm{mod}3\right)\\ 3& i\equiv 2\left(\mathrm{mod}3\right)\end{array}$

(2) 对于任意 $j\in \left\{1,2,\cdots ,t-1\right\}$，

$\psi \left(x_j{x}_{j+1}\right)=\{\begin{array}{cc}3& j\equiv 0\left(\mathrm{mod}3\right)\\ 2& j\equiv 1\left(\mathrm{mod}3\right)\\ 1& j\equiv 2\left(\mathrm{mod}3\right)\end{array}$

(3) $\psi \left(x_1{x}_t\right)=3$。

2. $t\ne 3k$，$k\in N$ 且t为奇数。

给图 $C_t$ 定义一个全染色 $\psi$ ：

(1) 对于任意 $i\in \left\{1,2,\cdots ,t\right\}$，

$\psi \left(x_i\right)=\{\begin{array}{cc}4& i\equiv 0\left(\mathrm{mod}2\right),i\ne t-1\\ 1& i\equiv 1\left(\mathrm{mod}2\right),i\ne t\\ 2& i=t-1\\ 3& i=t\end{array}$

(2) 对于任意 $j\in \left\{1,2,\cdots ,t-1\right\}$，

$\psi \left(x_j{x}_{j+1}\right)=\{\begin{array}{cc}2& j\equiv 0\left(\mathrm{mod}2\right),j\ne t-1\\ 3& j\equiv 1\left(\mathrm{mod}2\right)\\ 4& j=t-1\end{array}$

(3) $\psi \left(x_1{x}_t\right)=2$。

3. $t\ne 3k$，$k\in N$ 且t为偶数。

给图 $C_t$ 定义一个全染色 $\psi$ ：

(1) 对于任意 $i\in \left\{1,2,\cdots ,t\right\}$，

$\psi \left(x_i\right)=\{\begin{array}{cc}4& i\equiv 0\left(\mathrm{mod}2\right)\\ 1& i\equiv 1\left(\mathrm{mod}2\right)\end{array}$

(2) 对于任意 $j\in \left\{1,2,\cdots ,t-1\right\}$，

$\psi \left(x_j{x}_{j+1}\right)=\{\begin{array}{cc}2& j\equiv 0\left(\mathrm{mod}2\right)\\ 3& j\equiv 1\left(\mathrm{mod}2\right)\end{array}$

(3) $\psi \left(x_1{x}_t\right)=2$。

显然， $S\left[x_1,\psi \right]=\left[1,3\right]$ 且 $\psi \left(x_1\right)=1$。所以我们可以将边 $x_{1}w$ 染颜色4，然后将顶点u，v和w分别染颜色2，1，3，然后将边uw，vw和uv分别染颜色1，2，3。

情况2.2.4x与顶点w之间是一条路。令此路为 $P_m$ 且 $V\left(P_m\right)=\left\{y_1,y_2,\cdots ,y_m\right\}$，其中 $y_1=x_1$，$y_m=w$。

先用情况2.2.3中同样的方法染圈 $C_t$。然后将边 $y_1{y}_2$ 染颜色4。对于剩余顶点与边，染色规则与情况2.2.2中4的方法一样。

情况2.3 $\left|V\left(B\right)\right|=4$。

令顶点w是块B与割边的公共顶点。显然 $d_G\left(w\right)=3$。令 $N_B\left(w\right)=\left\{x,z\right\}$，顶点y是x和z的公共顶点。如果边 $xz\in E\left(G\right)$，那么染色规则与情况1一样。因此我们只需考虑 $B=C_4$。令 $w^{\prime }$ 为距离顶点w最近的3度点。我们先假设 $w^{\prime }$ 不在圈上。

情况2.3.1 顶点w与 $w^{\prime }$ 相邻。

对 $\left|V\left(G\right)\right|$ 进行归纳。如果 $\left|V\left(G\right)\right|=8$，定理显然成立。假设对于任意的外平面图H来说，定理成立，其中 $8<\left|V\left(H\right)\right|<\left|V\left(G\right)\right|$ 且 $\Delta \left(H\right)=3$，$\delta \left(H\right)=2$。令 $H=G-x-y-z-w$，由归纳假设知：H存在一个5-区间全染色点 $\phi$。令 $\phi \left(w{w}^{\prime }\right)=a$。

(1) $\phi \left(w{w}^{\prime }\right)=a\in \left\{1,5\right\}$。

如果 $\phi \left(w^{\prime }\right)\ne 2$，那么将顶点x，y，z和w分别染颜色5，2，5，2，然后将边xw，xy，yz和zw分别染颜色3，4，3，4。否则就将顶点x，y，z和w分别染颜色1，4，1，4，然后将边xw，xy，yz和zw分别染颜色2，3，2，3。

(2) $\phi \left(w{w}^{\prime }\right)=a\in \left\{2,3\right\}$。

如果 $\phi \left(w^{\prime }\right)\ne 1$，那么将顶点x，y，z和w分别染颜色2(4)，5(1)，2(3)，1(1)，然后将边xw，xy，yz和zw分别染颜色3(2)，4(3)，3(2)，4(4)。否则就将顶点x，y，z和w分别染颜色2(2)，5(5)，2(3)，4(4)，然后将边xw，xy，yz和zw分别染颜色1(1)，3(3)，4(4)，3(2)。

(3) $\phi \left(w{w}^{\prime }\right)=4$。

如果 $\phi \left(w^{\prime }\right)\ne 1$，那么将顶点x，y，z和w分别染颜色4，1，4，1，然后将边xw，xy，yz和zw分别染颜色2，3，2，3。否则就将顶点x，y，z和w分别染颜色4，1，4，5，然后将边xw，xy，yz和zw分别染颜色2，3，2，3。

情况2.3.2顶点 $w^{\prime }$ 与顶点w之间是一条路 $P_m$。令 $V\left(P_m\right)=\left\{w_1,w_2,\cdots ,w_m\right\}$，其中 $w_1=w^{\prime }$，$w_m=w$。

1. $\phi \left(w_1{w}_2\right)=1$。

给图G定义一个全染色 $\psi$ ：

(1) 对于任意 $i\in \left\{2,3,\cdots ,m-1\right\}$，

$\psi \left(w_i\right)=\{\begin{array}{cc}2& i\equiv 2\left(\mathrm{mod}3\right)\\ 1& i\equiv 0\left(\mathrm{mod}3\right)\\ 3& i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

(2) 对于任意 $j\in \left\{1,2,\cdots ,m-1\right\}$，

$\psi \left(w_j{w}_{j+1}\right)=\{\begin{array}{cc}1& j\equiv 1\left(\mathrm{mod}3\right)\\ 3& j\equiv 2\left(\mathrm{mod}3\right)\\ 2& j\equiv 0\left(\mathrm{mod}3\right)\end{array}$

如果 $\phi \left(w_1\right)=2$，那么交换(1)中染颜色2和3的顶点的颜色，且同时交换(2)中染颜色2和3的边的颜色。显然 $\psi \left(w_{m-1}{w}_m\right)=1$ 或2或3。

① $\psi \left(w_{m-1}{w}_m\right)=1$。

因为 $\psi \left(w_{m-1}\right)\ne 4$，那么将顶点x，y，z和w分别染颜色1，4，1，4，然后将边xw，xy，yz和zw分别染颜色2，3，2，3。

② $\psi \left(w_{m-1}{w}_m\right)\in \left\{2,3\right\}$。

因为 $\psi \left(w_{m-1}\right)\ne 4$，那么将顶点x，y，z和w分别染颜色2(2)，5(5)，2(3)，4(4)，然后将边xw，xy，yz和zw分别染颜色1(1)，3(3)，4(4)，3(2)。

2. $\phi \left(w_1{w}_2\right)\in \left\{2,3\right\}$。

在1中(1)和(2)的基础上，交换(1)中染颜色1(1)和2(3)的顶点的颜色，且同时交换(2)中染颜色1(1)和2(3)的边的颜色。假设新得到的全染色为 ${\psi }_1\left({\psi }_2\right)$。如果 $\phi \left(w_1\right)=1\left(2\right)$，那么在 ${\psi }_1\left({\psi }_2\right)$ 的基础上，交换(1)中染颜色1(1)和3(2)的顶点的颜色，且同时交换(2)中染颜色1(1)和3(2)的边的颜色。显然 ${\psi }_1\left(w_{m-1}{w}_m\right)=1$ 或2或3 $\left({\psi }_2\left(w_{m-1}{w}_m\right)=1,2,3\right)$。在各种子情况下，染色规则与1中①②③分别对应相同。

3. $\phi \left(w_1{w}_2\right)=4$。

给图G定义一个全染色 ${\psi }^{\prime }$ ：

(1) 对于任意 $i\in \left\{2,3,\cdots ,m-1\right\}$，

${\psi }^{\prime }\left(w_i\right)=\{\begin{array}{cc}2& i\equiv 2\left(\mathrm{mod}3\right)\\ 4& i\equiv 0\left(\mathrm{mod}3\right)\\ 3& i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

(2) 对于任意 $j\in \left\{1,2,\cdots ,m-1\right\}$，

${\psi }^{\prime }\left(w_j{w}_{j+1}\right)=\{\begin{array}{cc}4& j\equiv 1\left(\mathrm{mod}3\right)\\ 3& j\equiv 2\left(\mathrm{mod}3\right)\\ 2& j\equiv 0\left(\mathrm{mod}3\right)\end{array}$

如果 $\phi \left(w_1\right)=2$，那么交换(1)中染颜色2和3的顶点的颜色，且同时交换(2)中染颜色2和3的边的颜色。显然 ${\psi }^{\prime }\left(w_{m-1}{w}_m\right)=2$ 或3或4。因为 ${\psi }^{\prime }\left(w_{m-1}\right)\ne 1$，所以我们使用情况2.3.1中对应情况的染色规则来染剩余顶点与边。

4. $\phi \left(w_1{w}_2\right)=5$。

给图G定义一个全染色 ${\psi }^{″}$ ：

(1) 对于任意 $i\in \left\{2,3,\cdots ,m-1\right\}$，

${\psi }^{″}\left(w_i\right)=\{\begin{array}{cc}3& i\equiv 2\left(\mathrm{mod}3\right)\\ 5& i\equiv 0\left(\mathrm{mod}3\right)\\ 4& i\equiv 1\left(\mathrm{mod}3\right)\end{array}$

(2) 对于任意 $j\in \left\{1,2,\cdots ,m-1\right\}$，

${\psi }^{″}\left(w_j{w}_{j+1}\right)=\{\begin{array}{cc}5& j\equiv 1\left(\mathrm{mod}3\right)\\ 4& j\equiv 2\left(\mathrm{mod}3\right)\\ 3& j\equiv 0\left(\mathrm{mod}3\right)\end{array}$

如果 $\phi \left(w_1\right)=3$，那么交换(1)中染颜色3和4的顶点的颜色，且同时交换(2)中染颜色3和4的边的颜色。显然 ${\psi }^{″}\left(w_{m-1}{w}_m\right)=3$ 或4或5。因为 ${\psi }^{″}\left(w_{m-1}\right)\ne 1$ 且 ${\psi }^{″}\left(w_{m-1}\right)\ne 2$，所以我们使用情况2.3.1中对应情况的染色规则来染剩余顶点与边。

最后，我们考虑顶点 $w^{\prime }$ 在圈上。令此圈为 $C_s$ 且 $V\left(C_s\right)=\left\{y_1,y_2,\cdots ,y_s\right\}$，其中 $y_1=w^{\prime }$。

情况2.3.3 $d_G\left(y_1\right)=d_G\left(w^{\prime }\right)=3$ 且 $y_1$ 与w相邻。

先用情况2.2.3中染圈 $C_t$ 的方法来染圈 $C_s$。然后将边 $w{y}_1$ 染颜色4。对于剩余顶点与边，染色规则与情况2.3.1中(4)的方法一样。

情况2.3.4 $y_1$ 与顶点w之间是一条路。令此路为 $P_m$ 且 $V\left(P_m\right)=\left\{w_1,w_2,\cdots ,w_m\right\}$，其中 $w_1=y_1$，$w_m=w$。

先用情况2.2.3中染圈 $C_t$ 的方法来染圈 $C_s$。然后将边 $w_1{w}_2$ 染颜色4。对于剩余顶点与边，染色规则与情况2.3.2中3的方法一样。

最后我们考虑 $\delta =1$，即图G中存在叶子点，将其中一个叶子点记为u，将顶点u的邻点记为v。对图G顶点数 $\left|V\left(G\right)\right|$ 进行归纳，如果 $\left|V\left(G\right)\right|=2$，定理显然成立。假设对于任意的外平面图H来说，定理成立，其中 $2<\left|V\left(H\right)\right|<\left|V\left(G\right)\right|$ 且 $\Delta \left(H\right)=3$，$\delta \left(H\right)=2$。令 $H=G-u$，由归纳假设知：H存在一个5-区间全染色点 $\phi$。

情况3 $d_G\left(v\right)=2$。

(1) $S\left[v,\phi \right]=\left[1,2\right]$ 或 $\left[2,3\right]$。

因为 $\max \left(S\left[v,\phi \right]\right)+1$，$\max \left(S\left[v,\phi \right]\right)+2\notin S\left[v,\phi \right]$，所以我们可以将边uv和顶点u分别染颜色 $\max \left(S\left[v,\phi \right]\right)+1$，$\max \left(S\left[v,\phi \right]\right)+2$。

(2) $S\left[v,\phi \right]=\left[3,4\right]$ 或 $\left[4,5\right]$。

因为 $\min \left(S\left[v,\phi \right]\right)-1$，$\min \left(S\left[v,\phi \right]\right)-2\notin S\left[v,\phi \right]$，所以我们可以将边uv和顶点u分别染颜色 $\min \left(S\left[v,\phi \right]\right)-1$，$\min \left(S\left[v,\phi \right]\right)-2$。

情况4 $d_G\left(v\right)=3$。

(1) $S\left[v,\phi \right]=\left[1,3\right]$ $\left(\left[3,5\right]\right)$。

因为 $4,5\notin S\left[v,\phi \right]$ $\left(1,2\notin S\left[v,\phi \right]\right)$，所以将边uv和顶点u分别染颜色4(2)，5(1)。

(2) $S\left[v,\phi \right]=\left[2,4\right]$。

如果 $\phi \left(v\right)\ne 2$，所以将边uv和顶点u分别染颜色1，2。否则就将边uv和顶点u分别染颜色5，4。

情况2，情况3和情况4中剩余顶点和边的颜色与H中对应的顶点和边的颜色相同。显然，所得到的全染色均为图G的一个5-区间全染色且 $w_t\left(G\right)\le 5$。 £

文章引用

张乔慧,井普宁. 外平面图的区间全染色
The Interval Total Colorings of Outerplane Graphs[J]. 应用数学进展, 2021, 10(09): 2976-2987. https://doi.org/10.12677/AAM.2021.109312

参考文献