平面图的一种2-距离（2Δ+7）着色方案

《Discrete Applied Mathematics》：A 2-distance (2Δ+7)-colouring of planar graphs

　　摘要：图G的顶点着色被称为2-距离着色，如果任意两个相距不超过2的顶点都接收不同的颜色。最近，Bousquet等人（2023年）证明了对于最大度为Δ≥9的平面图，2Δ+7种颜色就足以进行2-距离着色。在本文中，我们通过取消最大度约束，加强了他们的结果，并表明所有平面图都存在2-距离（2Δ+7）着色。特别是，这改进了van den Heuvel和McGuinness（2003年）的研究成果。

引言：在与图相关的众多问题和概念中，着色是一个基本且被广泛研究的话题。图的顶点着色是为其顶点分配颜色，使得相邻的顶点接收不同的颜色。一种特别有趣的顶点着色变体是2-距离着色，其中任意两个相距2或更少的顶点都具有不同的颜色。这种着色的动机来自于某些实际问题中的需求，即不仅需要为相邻的顶点分配不同的颜色，还需要为那些位置接近的顶点分配不同的颜色[14]，[16]。2-距离着色的概念最初在[12]，[13]中被引入，并且由于某些问题（例如总着色猜想[5]中的详细内容）可以将其表述为特定图的2-距离着色而受到了相当多的关注。Cranston[5]对2-距离着色及其相关着色概念进行了全面的调查。图G能够接受的2-距离着色的最小颜色数被称为G的2-距离色数χ2(G)。1977年，Wegner[19]提出了以下猜想：

猜想1.1：对于每一个最大度为Δ的平面图G，如果Δ=3，则χ2(G)≤7；如果4≤Δ≤7，则χ2(G)≤Δ+5；如果Δ≥8，则χ2(G)≤?3Δ2?+1。

Wegner的猜想是图着色领域中最著名的问题之一，多年来一直没有得到解决，除了Δ=3的情况，该情况由Thomassen[18]（以及Hartke等人[9]独立地）解决。据证明，对于较大的Δ值，该猜想也是渐近正确的[1]，[10]。对于一般的平面图，van den Heuvel和McGuinness[11]表明χ2(G)≤2Δ+25，而Molloy和Salavatipour[17]证明了χ2(G)≤?5Δ3?+78。另一方面，在对最大度或周长有限制的情况下，也获得了几个改进的结果[3]，[4]，[6]，[7]，[8]。特别是，Bousquet等人[2]表明如果Δ≥9，则χ2(G)≤2Δ+7，这大大改进了[15]中的工作。更近期，Yu和Chen[21]表明当Δ≥8时，χ2(G)≤2Δ+6。对于最大度较小的平面图，Bousquet等人[3]证明了当Δ≤4时，χ2(G)≤12；而Deniz[8]证明了当Δ≤5时，χ2(G)≤16。在本文中，我们通过取消最大度约束，加强了Bousquet等人[2]的结果，并表明所有平面图都存在2-距离（2Δ+7）着色，这特别改进了van den Heuvel和McGuinness[11]所提供的最佳界限2Δ+25。

定理1.2：对于每一个平面图G，我们有χ2(G)≤2Δ+7。

本文中的所有图都被假设为简单的图，对于未在此定义的术语和符号，我们参考[20]。当G是平面图时，我们使用V(G)，E(G)，F(G)和Δ(G)分别表示顶点集、边集和面集以及G的最大度。如果上下文中没有混淆，我们将Δ(G)简写为Δ。对于一个正整数t，我们用[t]表示1到t之间的整数集合。给定一个平面图G，我们用?(f)表示面f的长度，用d(v)表示顶点v的度数。k-顶点是度数为k的顶点。k?-顶点是度数最多为k的顶点，而k+-顶点是度数至少为k的顶点。k (k?或k+)面与顶点类似定义，其中面的度数是指与它相连的边数。如果d(u)=k（分别d(u)≤k或d(u)≥k），则称顶点u∈N(v)是v的k-邻居（分别为k?-邻居或k+-邻居）。

对于V(G)中的顶点v，我们用ni(v)表示与v相邻的i-顶点的数量。我们用d(u,v)表示u和v之间的距离。此外，我们定义Ni(v)?{u∈V(G)|1≤d(u,v)≤i}，其中i≥1，因此N1(v)=N(v)，并令d2(v)=|N2(v)|。对于V(G)中的v，我们用mk(v)表示与v相连的k-面的数量。如果一个k-顶点v的m3(v)=d，则称其为k(d)-顶点。特别地，如果m3(v)≤d，则称k-顶点v为k(d?)-顶点（分别为k(d+)-顶点）。如果两个面f1和f2共享一条边，则称它们为相邻的面。

定理1.2的证明：设G是定理1.2的一个最小反例，使得|V(G)|+|E(G)|最小。因此，G不接受任何2-距离（2Δ+7）着色，而任何从G获得的新的平面图G′（满足|V(G′)|+|E(G′)|<|V(G)|+|E(G)|）都接受2-距离（2Δ+7）着色。根据[3]，[8]，[21]的结果，我们只需考虑6≤Δ≤7的情况。显然，G是连通的。接下来我们引入一个结构最小性的概念：如果图H是平面的并且可以从G获得，则称H为相对于G是适当的。

致谢：作者感谢Kengo Aoki指出了之前版本中引理2.3的一个重大错误。作者还要感谢匿名审稿人的仔细阅读和宝贵的评论和建议，这些帮助识别了几个错误，并显著提高了本文的正确性和表达效果。