不含三角形4-圈和三角形5-圈的平面图的分数染色

《Discrete Mathematics》：Fractional coloring of planar graphs with neither triangular 4-cycles nor triangular 5-cycles

　　摘要
图G的分数色数χf(G)定义为所有比值s/t的下确界，其中s/t使得可以为G的每个顶点分配{1,2,…,s}的一个t-子集，且相邻顶点获得不相交的子集。图G的独立数α(G)是G的最大独立集的大小，而G的独立比定义为|V(G)|/α(G)。众所周知，|V(G)|/α(G)≤χf(G)。新西伯利亚三色猜想断言：每个不含与长度为4或5的环共用一条边的三角形的平面图都是3-可染的。Cohen-Addad等人(2017) [6] 证明该猜想为假。Kelly等人(2026) [16] 证明每个这样的图其独立比至多为4?29，并猜想存在某个ε>0，使得每个既不含三角形4-环也不含三角形5-环的平面图G满足χf(G)≤4?ε。在本文中，我们证明每个此类平面图的分数色数至多为11/3，因此其独立比至多为4?13。

引言
图G的正常k-染色是映射?:V(G)→{1,…,k}，使得相邻顶点获得不同的颜色。图G的色数χ(G)是使得存在这种染色的最小k值。四色定理断言每个平面图都是4-可染的。对于给定的平面图G且E(G)≠?，我们有χ(G)∈{2,3,4}；G是2-可染的当且仅当G是二部图。Gr?tzsch [14] 证明了若G是无三角形图，则G是3-可染的。然而，在1976年，Garey、Johnson和Stockmeyer [13] 表明确定一个平面图是否为3-可染是NP-完全的。许多作者 [1], [2], [4], [5] 通过允许三角形并附加结构限制，研究了平面图3-可染的其他充分条件。1976年，Steinberg [17] 提出了以下著名猜想。

猜想1.1 [17] 每个不含长度为4或5的环的平面图都是3-可染的。

两个环若共用一条边则称为相邻。若一个环与一个三角形共用一条边，则称为三角形环。Borodin和Raspaud [5] 在2003年提出了强波尔多猜想，该猜想蕴含Steinberg猜想；它断言：每个既不含5-环也不含相邻三角形的平面图是3-可染的。随后Borodin等人 [3] 提出了新西伯利亚猜想。

猜想1.2 [3] 每个既不含三角形4-环也不含三角形5-环的平面图都是3-可染的。

若新西伯利亚猜想成立，则蕴含强波尔多猜想和Steinberg猜想。然而，由于Steinberg猜想为假 [6]，强波尔多猜想和新西伯利亚猜想也为假。

放宽Steinberg猜想的一种方式是考虑分数染色。(s:t)-染色为每个顶点分配{1,…,s}的一个t-子集，使得相邻顶点获得不相交的子集。分数色数χf(G)是使得这种染色存在的最小比值s/t。显然χf(G)≤χ(G)。分数染色由Hilton等人 [15] 引入，旨在证明四色问题。他们证明了每个平面图的分数色数小于5。此后，许多研究者研究了平面图的分数染色。Cranston和Rabern [8] 给出了一个不借助计算机且独立于四色定理的证明，证明了每个平面图的分数色数至多为92。Dvo?ák等人 [12] 证明了每个n顶点无三角形平面图的分数色数至多为3?33n+1；他们还猜想每个围长至少为5的平面图的分数色数至多为3?ε，其中ε>0为某个常数。后来，Dvo?ák和Hu [10] 将该上界改进为3?32n+1，并证明了存在常数MΔ，使得每个围长至少为5且最大度为Δ的平面图G满足χf(G)≤3?32MΔ+1。Dvo?ák和Hu [9] 证明了每个不含4-环或5-环的平面图的分数色数至多为113。事实上，他们建立了以下列表染色结果。

定理1.3 [9] 每个不含长度为4或5的环的平面图是(11:3)-可选择的，因此χf(G)≤113。

Steinberg猜想的另一个自然放宽由独立数给出。独立数α(G)是G中最大独立集的大小，G的独立比定义为|V(G)|/α(G)。众所周知，|V(G)|/α(G)≤χf(G)≤χ(G)。在不使用四色定理的情况下，Cranston和Rabern [7] 证明了每个平面图的独立比至多为133。Gr?tzsch定理蕴含无三角形平面图的独立比至多为3。Steinberg和Tovey [18] 证明了每个n顶点无三角形平面图都有一个大小为?n3?+1的独立集。Dvo?ák和Mnich [11] 改进了该结果，证明了n+13是此类平面图独立数的紧下界。Dvo?ák和Hu [9] 证明了不含4-环或5-环的平面图的独立比至多为11/3。最近，Kelly等人 [16] 研究了既不含三角形4-环也不含三角形5-环的平面图的独立比。

定理1.4 [16] 每个既不含三角形4-环也不含三角形5-环的平面图的独立比至多为4?29。

他们还提出了以下猜想。

猜想1.5 [16] 存在某个ε>0，使得每个既不含三角形4-环也不含三角形5-环的平面图的分数色数至多为4?ε。

注意，猜想1.5是猜想1.2的较弱版本。在本文中，我们确认在猜想1.5中可取ε=13。

定理1.6
设G是既不含三角形4-环也不含三角形5-环的平面图。则G是(11:3)-可染的，因此χf(G)≤113。由此，既不含三角形4-环也不含三角形5-环的平面图的独立比至多为4?13。

注
我们的结果不仅对猜想1.5给出了肯定回答，还改进了定理1.4中的界。此外，定理1.6为比定理1.3所考虑类别更广的平面图类建立了(11:3)-可染性。

我们以贯穿全文的记号来结束引言。设G=(V(G),E(G))是平面图，其面集为F。对每个面f∈F，d(f)表示其面边界的长度，f也表示其边界顶点集。唯一无界面为外界面，其他面均为内面。对于顶点v∈V(G)，用NG(v)和d(v)分别表示其邻域和度。若一个顶点不与外界面相关联，则称为内部顶点；否则称为外部顶点。k-顶点、k+-顶点和k?-顶点分别指度为k、至少k和至多k的顶点。同样的记号也适用于面和环。对于S?V(G)，用G[S]表示由S诱导的G的子图。对于环C，用int(C)和ext(C)分别表示C内部和外部的顶点集。我们记Int(C)=G?ext(C)和Ext(C)=G?int(C)为相应的诱导子图。若环C的int(C)和ext(C)均非空，则称C为分离环。若G的一条边或一个顶点位于某个三角形中，则称其为三角形边或三角形顶点。对于{u,v}?V(G)且uv?E(G)，收缩{u,v}意味着用单个顶点uv_替换u和v，该顶点与所有与{u,v}中至少一个顶点相关联的边相关联；得到的图记为G/{u,v}。

预备知识
在本节中，我们首先引入(L:3)-可染图的定义，然后给出一些将在定理1.6证明中使用的技术引理。
设L={L(v):v∈G}为一组列表，每个列表L(v)由与G的每个顶点v相关联的若干元素组成。设?为给G的每个顶点v分配L(v)的一个3-子集，使得对于G的每条边uv，?(u)∩?(v)=?。我们称这样的分配?为G的一个(L:3)-染色，若G具有(L:3)-染色，则称G是(L:3)-可染的。

主要结果的证明
在本节中，我们将给出定理1.6的证明。事实上，我们将建立一个更强的版本，其中外界面是预染的。设G是既不含三角形4-环也不含三角形5-环的平面图。
G中的一个环C称为G的特殊环，若|C|∈{6,7}且满足以下条件之一：
(1)存在一个顶点x?V(C)，使得x在V(C)上至少有三个邻居；
(2)存在G?V(C)的一条边xy，使得|N(x)∩V(C)|≥2且|N(y)∩V(C)|≥2。
满足(1)的顶点x称为Yue Lyu|Xiaolan Hu