DOI:10.19789/j.1004-9398.2023.01.001

文献引用:樊亚飞,张玉琴 .可平面图的 DP-3-染色[J].首都师范大学学报(自然科学版),2023,44(1):1-10.FAN Y F,ZHANG Y Q.DP-3-coloring of some planar graphs[J].Journal of Capital Normal University(Natural Science Edition),2023,44(1):1-10.

可平面图的DP-3-染色*

樊亚飞**,张玉琴

(天津大学数学学院,天津 300354)

摘要:Dvořák和Postle首次提出了DP-染色,该染色是列表染色的推广。本文证明了每个无{4,5,7,10}-圈的可平面图和每个无{4,5,8,10}-圈的可平面图都是 DP-3-可染的,对这些可平面图的3-可选性进行了推广。

关键词:列表染色;DP-染色;可平面图;权转移规则

DP-3-coloring of some planar graphs*

FAN Yafei**,ZHANG Yuqin
(School of Mathematics,Tianjin University,Tianjin 300354)

Abstract:DP-coloring is a generalization of list coloring,which was introduced by Dvořák and Postle.In this paper,we show that every planar graph without cycles of length{4,5,7,10}and every planar graph without cycles of length{4,5,8,10}are DP-3-colorable,which extend the corresponding results on 3-choosability.

Keywords:list coloring;DP-coloring;planar graph;discharging rules

CLC:O157.5 DC:A

中图分类号:O157.5

文献标识码:A

收稿日期:2022-02-09

*国家自然科学基金项目(11971346)

**通信作者:18230403021@163.com

0 引 言

本文所涉及的图都是无向的简单图。令G是一个平面图,其顶点集为V(G),边集为E(G),面集为F(G)。图G的最大度和最小度分别表示为Δ(G)和δ(G)。如果两个面有一个公共边,则称这两个面相邻。若两个相邻面只有两个公共顶点,则称为正规相邻;否则,称为非正规相邻。对于v∈V(G),顶点的度d(v)表示v关联的边数。对于f∈F(G),面的度d(f)表示f关联的边数。用b(f)表示 f的边界回路,且若 v1,v2,…,vk是 b(f)上的顶点,则记f=[v1v2…vk]。如果b(f)形成一个圈,则称f为简单面;否则,称f为非简单面。若顶点v的度为 k(至少为k,至多为k),则称v为k-顶点(k--顶点,k+-顶点)。若面f的度为k(至少为k,至多为k),则称 f为k-面(k--面,k+-面)。若 f=[v1v2…vk],vi=di(i=1,2,…,k),则 称 f为 (d1,d2,…,dk)-面 。 若e=v1v2,vi=di(i=1,2),则称 e为(d1,d2)-边。

G的真k-着色是一个映射c:V(G)→[k]使得对任意的边 uv∈ E(G),有 c(u)≠ c(v),其中[k]={1,2,…,k}。使得G有一个真k-着色的最小整数k称为G的染色数,并记为χ(G)。

Vizing[1]和 Erdős等[2]分别提出了列表染色。G的一个列表分配是一个函数L:V(G)→N,对每个顶点v∈V(G)分配一个颜色列表L(v)。如果每个顶点的颜色列表的大小为k,则称L是一个k-列表分配。G的一个L-着色是一个函数 φ:使得对每个顶点v∈V(G),有φ(v)∈L(v), 且 对 每 条 边 uv∈E(G), 有φ(u)≠φ(v)。如果G对每个k-列表分配L都有一个L-着色,则称G是k-可选的。使得G是k-可选的最小整数k称为其列表染色数,记为χℓ(G)。如果对所有的顶点 v ∈ V(G),令 L(v)=[k],则 L-染色就是一个真 k-着色,因此 χ(G) ≤ χℓ(G)。Thomassen[3-4]证明了每个可平面图是5-可选的且每个围长至少为 5的可平面图是 3-可选的;Voigt课题组[5-6]证明了存在非4-可选的平面图和非3-可选的围长为4的平面图,使得平面图是3-可选的充分条件被广泛研究,Dvořák 和 Postle[7]提出了 DP-染色的概念,该染色是列表染色的推广。

定义1[7] 令G是一个简单图,L是G的一个列表分配,对每个顶点u ∈ V(G),令Lu={u}× L(u)。对每条边uv∈E(G),令Muv是集合Lu和Lv之间的匹配(可能为空)且令ML={Muv:uv∈ E(G)},并称ML为匹配分配。令H是满足下列条件的图:

(a);

(b)对每个顶点u∈V(G),集合Lu形成一个团;

(c)如果uv ∈ E(G),则Lu和Lv之间的边是Muv;

(d)如果uv ∉ E(G),则Lu和Lv之间不存在边。

假设f:V(G)→ Ν 是一映射,若对每个顶点u∈ V(G),|L(u)|=f(u),则称序对 (H,L)是 G 的一个f-覆盖。如果H包含一个大小为|V(G)|的独立集,则G有一个ML-着色。如果对每个k-列表分配L和每个匹配分配ML,G都有一个ML-着色,则称G是DP-k-可染的。使得G是DP-k-可染的最小整数k称为DP-染色数,记为χDP(G)。如果定义H的边是对每个uv∈E(G),恰匹配Lu和Lv中相同的颜色,则G有一个ML-着色当且仅当G是L-可染的,因此χℓ(G) ≤ χDP(G)。此 外 ,χDP(G)- χℓ(G)可 以 任意大。特别地,Bernshteyn[8]证明了平均度为 d 的二部图的DP-染色数为,然而 Alon[9]证明了χℓ(Kd,d)=O(logd)。

近几年,图的DP-染色数的概念引起了广泛的关 注 。例如,Bernshteyn 和 Kostochka[10]证明了 DP-临界可染图的边数的最小值;Bernshteyn等[11]提出了多重图的DP-染色并且刻画了非DP-度-可染的多重图;Bernshteyn等[12]证明了对于 n-顶点图 G,当 G的染色数接近于n时,该图的DP-染色数等于其染色数;Dvořák 和 Postle[7]证明了每个平面图都是 DP-5-可染的且每个无3-圈和4-圈的平面图是DP-3-可染的。在文献[13-15]中给出一些使得可平面图是DP-4-可染的充分条件;在文献[16-18]中给出一些使得可平面图是DP-3-可染的充分条件。下列定理是使得可平面图是3-可选的充分条件。

定理1 如果可平面图G满足下列条件之一,则G是3-可选的。

(1)G 不包含{4,5,7,10}-圈[19];

(2)G 不包含{4,5,8,10}-圈[20]。

本文将此定理进行了推广,即证明了下列定理。

定理2 如果可平面图G满足下列条件之一,则G是DP-3-可染的。

(1)G不包含{4,5,7,10}-圈;

(2)G不包含{4,5,8,10}-圈。

1 极小非DP-k-可染图的性质

如果图G不是DP-k-可染的,但其任意真子图是DP-k-可染的,则称图G是极小非DP-k-可染的。

引理1[9] 如果图G是极小非DP-k-可染的,则δ(G)≥ k。

引理2[11] 令k≥3且H是G的一个子图,假设G-H有一个DP-k-染色。如果H的顶点可以排序为 v1,v2,…,vl使得下列条件成立:

(1)v1vl∈ E(G)且|A(v1)|> |A(vl)|≥ 1,其 中A(v)表示在G-H完成染色后,v的可用颜色所构成的集合;

(2)d(vl)≤ k且vl在G-H中至少有1个邻点;

(3)对任意的 2≤i≤l-1,vi在图 G[{v1,…,vi-1}]∪(G-H)中至多有k-1个邻点,则G-H的染色可以扩展为G的DP-k-染色。

令v是一个3-顶点,若v恰关联1个3-面,则称v是poor-3-顶点;若v恰关联1个4-面,则称v是semirich-3-顶点;若v不关联任何4--面,则称v是rich-3-顶点。令v是一个4-顶点,若v恰关联2个3-面,则称v是weak-4-顶点;若v恰关联1个3-面,则称v是semi-weak-4-顶点;若v不关联任何3-面,则称v是strong-4-顶点。如果k-面f关联的顶点均为3-顶点,则称f为light-k-面;否则,称f为非light-k-面。如果k-面f恰关联1个4+-顶点且其余顶点均为3-顶点,则称 f为 minimal-k-面。

引理3 如果G是极小非DP-3-可染的平面图且f是一个light-面,则f不相邻于light-面g。

证明 令 d(f)=k,d(g)=l,f=[v1v2…vk]且g=[v1v2w3…wl]使得 v1v2是 f和 g 的公共边,且 f和g所关联的顶点都是3-顶点。将f和g的顶点排序为v1,wl,…,w3,v2,v3,…,vk。令 H 是上述顶点所导出的子图,则根据G的极小性可知,G-H存在DP-3-染色。再由引理2可知,G-H的每个DP-3-染色都可以扩展为G的DP-3-染色,这与G是非DP-3-可染的相矛盾。

2 无{4,5,7,10}-圈的可平面图的DP-3-可染性

定理 3 每个无{4,5,7,10}-圈的可平面图是DP-3-可染的。

首先假设该定理不成立,则可令G是最小反例,即 G是极小非 DP-3-可染的且不含{4,5,7,10}-圈。由引理1可知δ(G)≥3。再结合图G中圈的限制可以得到下列引理所示的图G的可约构型。

引理4 图G满足下列性质:

(1)3-面不能相邻于3-面;

(2)3-面不能相邻于6-面;

(3)3-面不能相邻于9-面;

(4)3-面只能正规相邻于8-面,且每个8-面至多相邻于1个3-面。

证明 (1)如果3-面相邻于1个3-面,则将产生一个4-圈,这与G不含4-圈相矛盾。

(2)令f1是一个6-面,如果f1的边界是由2个3-圈构成的,即 f1=[v1v2v3v4v5v3],则由(1)可知 f1不能相邻于任何的3-面。因此不妨假设f1=[v1v2v3v4v5v6]且 f2=[v1v2w12]是 1个 3-面。令 S={v3,v4,v5,v6}。若 w12 ∉ S,则 v1w12v2v3v4v5v6是 1 个7-圈,矛盾。显然,w12 ≠ v3,否 则 G 包 含 5-圈v1v3v4v5v6,下面证明 w12 ≠ v4。如果 w12= v4,则G包含4-圈v1v6v5v4,矛盾。根据对称性易知w12 ∉ {v5,v6}。

(3)令f1是一个9-面,如果f1的边界是由1个6-圈和 1个3-圈或 3个 3-圈构成的,则由(1)和(2)可知f1不能相邻于任何的3-面。不妨假设f1=[v1v2…v9]且假 设 f2=[v1v2w12]是 1 个 3-面,令 S={v3,v4,…,v9},若 w12∉ S,则 v1w12v2v3…v9是 1 个10-圈,矛盾。首先,证明 w12≠ v3,否则 d(v2)=2。又因为 G不含 4-圈和 5-圈,所以 w12≠ v4,w12≠ v5,w12 ≠ v6。综上可知 w12 ∉ {v3,v4,v5,v6}。由对称性可知 w12 ∉ {v7,v8,v9}。

(4)令f1是一个8-面,因为G不含4-圈和5-圈,所以可假设且假设f1=[v1v2…v8]且假设f2=[v1v2w12]是 一 个 3-面 。 令 S={v3,v4,…,v8},若w12=v3,则d(v2)=2,矛盾。又因为G不含4-圈和5-圈,所以w12 ≠ v4,w12 ≠ v5。由对称性可知w12 ∉ {v6,v7,v8}。因此,f1不能非正规相邻于f2。

假设存在另1个3-面f3=[v1v8x]正规相邻于f1。若x≠w12,则将产生10-圈,这与G不含10-圈相矛盾;若 x=w12,则 G包含 4-圈 v8v1v2w12,矛盾。当 f3与 f1相邻 于 边 vivj(vivj∈{v7v8,v6v7,v5v6,v4v5,v3v4,v2v3})时,仍然可以得到矛盾。因此每个8-面至多相邻于1个 3-面。

现在对图G的顶点和面赋予初始权函数。对任意的v∈V(G),令ch(v)=d(v)-6;对任意的f ∈ F(G),令 ch(f)=2d(f)-6,因此,根据欧拉公式可知(2d(f)-6)=-12,即总的权和为-12。下面将设置适当的权转移规则,且用ch*表示最终权函数使得对任意的 x∈V(G)∪ F(G),有 ch*(x)≥0。 因 此 ,0≤ch*(x)=-12,矛盾。

权转移规则如下所示:

R1 令v是一个3-顶点,

R1.1 若v是poor-3-顶点,则v从每个关联的6+-面中各得。

R1.2 若v是rich-3-顶点,则v从每个关联的6+-面中各得1。

R2 令v是一个4-顶点,

R2.1 若v是weak-4-顶点,则v从每个关联的6+-面中各得1。

R2.2 若v是semi-weak-4-顶点,则v从每个关联的6+-面中各得,其中6+-面相邻于v所关联的3-面;且从其他的关联的6+-面中得。

R2.3 若v是strong-4-顶点,则v从每个关联的6+-面中各得。

R3 令v是一个5-顶点,则v从每个关联的6+-面中各得。

为了完成定理的证明,现证明每个顶点以及每个面的最终权值非负。

下面验证对任意的v∈V(G),有ch*(v)≥0。

令v是G中的任意顶点,由引理1可知d(v)≥3。

若d(v)≥6,则由于权转移规则中未涉及6+-顶点可知ch*(v)=ch(v)=d(v)-6≥0。

若 d(v)=5,则由引理 4(1)可知 v至多关联 2个3-面,即v至少关联3个6+-面。因此,由R3可知。

若 d(v)=4,则由引理 4(1)可知 v至多关联 2个3-面。如果v恰关联2个3-面,则v是weak-4-顶点且由R2.1可知ch*(v)=ch(v)+1×2=0;如果v恰关联1个3-面,则v是semi-weak-4-顶点且由R2.2可知;如果 v不关联任何的3-面,则v是strong-4-顶点且由R2.3可知。

若 d(v)=3,则由引理 4(1)可知 v至多关联 1个3-面。如果v是poor-3-顶点,则由R1.1可知;如果 v是 rich-3-顶点,则由R1.2可知ch*(v)=ch(v)+1×3=0。

现只需验证对任意的f∈F(G),有ch*(f)≥0。

令f是G中的任意面,因为G是简单图,所以d(f)≥3。若f是3-面,由于权转移规则中未涉及到 3-面,所以 ch*(f)=ch(f)=0。

若 d(f)=6,则由引理 4(2)可知 f不关联任何的poor-3-顶点,所以ch*(f)≥ ch(f)-1× 6=0。

若 d(f)=8,则由引理 4(4)可知 f至多关联 2个poor-3-顶点。因此,6=1> 0。

若d(f)=9,则由引理4(3)可知f不关联任何的poor-3-顶点。因此,ch*(f)≥ ch(f)-1× 9=3> 0。

若d(f)=11,则需要考虑2种情形:若f至少相邻于6个3-面,则由引理4(1)可知f至少关联1个4+-顶点,因此,;若f至多相邻于5个3-面,则f至多关联10个poor-3-顶点,所以。

若d(f)≥ 12,则。

3 无{4,5,8,10}-圈的可平面图的 DP-3-可染性

定理 4 每个无{4,5,8,10}-圈的可平面图是DP-3-可染的。

首先假设该定理不成立,则可令G是最小反例,即 G是极小非 DP-3-可染的且不含{4,5,8,10}-圈。由引理1可知δ(G)≥3。再结合图G中圈的限制可得下列引理所示的图G的可约构型。

引理5 图G满足下列性质:

(1)3-面不能相邻于 3-面;

(2)3-面不能相邻于 7-面;

(3)3-面只能非正规相邻于10-面,且每个10-面至多相邻1个3-面;

(4)3-面只能正规相邻于6-面,且每个6-面至多相邻于1个3-面。

证明 (1)如果3-面相邻于1个3-面,则将产生1个4-圈,这与G不含4-圈相矛盾。

(2)令f1是一个7-面,由G不含4-圈可假设f1=[v1v2v3v4v5v6v7]且f2=[v1v2w12]是一个3-面。令S={v3,v4,v5,v6,v7},若 w12 ∉ S,则 v1w12v2v3v4v5v6v7是1个 8-圈,矛盾。显然,w12≠ v3,否则d(v2)=2,这与δ(G)≥3矛盾。下面证明w12≠v4。如果w12=v4,则G包含4-圈v1v2v3v4,矛盾。根据对称性易知w12 ∉ {v5,v6,v7}。

(3)令f1是一个10-面,由G不含{4,5,10}-圈可知f1的边界是由1个7-圈和1个3-圈构成,则可假设f1=[v1v2…v7v1v8v9]。由(1)和(2)可知 f1只能相邻于 3-面 g=[v7v1v2]。

(4)令f1是一个6-面,如果f1的边界是由2个3-圈构成的,则由(1)可知f1不与任何3-面相邻。因此,可假设f1=[v1v2…v6]且f2=[v1v2w12]是一个3-面 。 令 S={v3,v4,v5,v6},若 w12=v3,则 G 包 含 5-圈v1v3v4v5v6,矛盾。下面证明w12≠v4。如果w12=v4,则G包含4-圈v1v2v3v4,矛盾。由对称性可知w12 ∉ {v5,v6}。因此,f1正规相邻于 f2。

假设存在另一个3-面f3=[v1v6x]正规相邻于f1。若x ≠ w12,则将产生8-圈,这与G不含8-圈相矛盾;若 x=w12,则 G 包含 4-圈 v6v1v2w12,矛盾。由对称性可知,当f3与f1相邻于边vivi+1(i∈ {2,3,4,5})时,仍然可以得到矛盾。因此每个6-面至多相邻于1个3-面。

引理6 任意2个简单6-面不能相邻。

证明 假 设 f1=[v1v2…v6]相 邻 于 f2=[v1v2u3…u6]。如果f1正规相邻于f2,则G包含一个10-圈。因此,假设这2个面非正规相邻。显然,v3≠ u3,否则d(v2)=2。因为G不含4-圈和5-圈,所以任意的6-圈都没有弦。所以u3 ∉{v3,v4,v5,v6}。由对称 性 可 知 u6 ∉ {v3,v4,v5,v6},v6 ∉ {u3,u4,u5,u6}且v3 ∉ {u3,u4,u5,u6}。下证 v4 ≠ u4且 v4 ≠ u5,否则,图G包含一个4-圈v2v3u4u3或一个5-圈v2v3v4u4u3。由对称性可知 v5 ∉ {u4,u5}。因此,f1不能相邻于 f2。

引理7 简单9-面不能相邻于3-面。

证明 假设f1=[v1v2…v9]是一个简单9-面且令 f2=[v1v2w12],S={v4,v5,…,v8}。 如 果 w12=v3或w12=v9,则d(v2)=2或d(v1)=2,矛盾。因为G不含{4,5,8}-圈,所以任意的 9-圈都没有弦。因此,w12∉S,即任意的简单9-面不能与3-面相邻。

引理 8 令 f1和 f2都是 G 中的 (3,3,3,3,3,4)-面且 f1与(3,3,4)-面 f3相邻于某(3,4)-边,则 f2不能与 f3相邻于另一(3,4)-边。

证 明 不 妨 假 设 f1=[v1v2v3v4v5v6],f2=[v1u3u4u5u6u7]且 f3=[v1v2u3]。将 f1,f2和 f3所关联的顶点进行排序,序列为 v1,u7,u6,u5,u4,u3,v2,v3,v4,v5,v6。令H是上述序列所导出的子图。根据G的极小性可知G-H是DP-3-可染的。由引理2可知G-H的每个DP-3-染色都可以扩展为G的DP-3-染色,矛盾。

引理 9 若 f1是 light-11-面且与 (3,3,4)-面 f2和(3,3,3,3,3,4)-面 f3都相邻,则 f3不能与 f2相邻于(3,4)-边。

证明 不妨假设f1=[v1v2…v11],f2=[v1v2u3]且 f3=[v2v3w1w2w3u3]。将 f1,f2和 f3所关联的顶点进行排序,序列为 v1,u3,v2,w3,w2,w1,v3,v4,…,v11。令H是上述序列所导出的子图。根据G的极小性可知G-H是DP-3-可染的,由引理2可知G-H的每个DP-3-染色都可以扩展为G的DP-3-染色,矛盾。

现在对图G的顶点和面赋予初始权函数。对任意的 v∈ V(G),令 ch(v)=d(v)-4;对任意的f ∈ F(G),令 ch(f)=d(f)-4。因此,根据欧拉公式可得总权和为-12。下面将设置适当的权转移规则,且用ch*表示最终权函数使得对任意的x∈V(G)∪F(G),有ch*(x)≥0。因此可得矛盾。

若 light-6-面通过 (3,3)-边与一个 3-面相邻,则称该 6-面是 worst-6-面;若 minimal-6-面通过 (3,3)-边与一个3-面相邻,则称该6-面是worse-6-面;若minimal-6-面通过 (3,4+)-边与一个 3-面相邻,则称该6-面是bad-6-面;若6-面恰关联2个4+-顶点且通过(4+,4+)-边与一个 3-面相邻,则称该 6-面是 semibad-6-面;其余的 6-面称为 good-6-面。

权转移规则如下所示。

R1 令v是一个3-顶点,

R1.1 若v是poor-3-顶点,则v从每个关联的6+-面中各得。

R1.2 若v是rich-3-顶点,则v从每个关联的6+-面中各得。

R2 令f是一个3-面,则f从每个关联的5+-顶点v中各得,其中t(v)表示v所关联的3-面的个数。

R3 令f是一个6-面,

R3.1 若f是worst-6-面,则f从相邻的11+-面中得,其中11+-面相邻于该6-面所相邻的3-面。

R3.2 若f是bad-6-面,则f给每个相邻的3-面各。

R3.3 若f是semi-bad-6-面,则f给每个相邻的3-面各。

R3.4 若f是good-6-面,则f给每个相邻的3-面各。

R4 令f是一个9+-面且g是相邻于f的3-面,

R4.1 若g至少关联1个5+-顶点,则当g相邻于worst或 worse-6-面时,f给;否则,f给。

R4.2 若g不关联任何的5+-顶点,则当g相邻于worst、worse或 bad-6-面时,f给;当g相邻于semibad-6-面时,f给;否则,f给。

为了完成定理的证明,现证明每个顶点以及每个面的最终权值非负。

下面验证对任意的v∈V(G),有ch*(v)≥0。

令v是G中的任意顶点,由引理1可知d(v)≥3。

若 d(v)≥5,则由 R2可知 ch*(v)=ch(v)-。

若d(v)=4,由于权转移规则中未涉及到4-顶点,所以ch*(v)=ch(v)=d(v)-4=0。

若d(v)=3,则需考虑2种情形。如果v关联一个3-面,则由引理5(1)可知其他2个关联面为6+-面。因此,由R1.1可知ch*(v)=ch(v)+×2=0。如果v不关联3-面,则由R1.2可知ch*(v)=ch(v)+× 3=0。

断言 令f是一个k-面且k≥11,若f关联x个4+-顶点,则当k+x≥16是偶数或k+x≥14是奇数时,ch*(f)≥ 0。

证明若f相邻于m个worst-6-面,则由引理5(4)可知f至少关联m个rich-3-顶点。且由引理5(1)可知f至多相邻个 3-面。由 R1、R3.1和 R4可知,

现只需验证对任意的f∈F(G),有ch*(f)≥0。

令f是G中的任意面,因为G是简单图,所以d(f)≥3。若d(f)≥16,则由上述断言可知ch*(f)≥0。

(1)d(f)=3。

因为G不含相邻的3-面,所以。如果f至少关联两个5+-顶点,则由R2可知ch*(f)≥ch(f)+×2=0。如果f恰关联 1 个 5+-顶点 ,则当 f相邻 1 个 worst或 worse-6-面时,由R2、R4.1和引理6可知ch*(f)≥ ch(f)++×2=0;否则,由 R2、R3和 R4.1可知 ch*(f)≥ch(f)++×3=0。

如果f恰关联3个4-顶点,则当f相邻1个semibad-6-面时,由 R3和 R4.2可知 ch*(f)≥ch(f)++×2=0;否则由 R3和 R4.2可知 ch*(f)≥ch(f)+× 3=0。

如果f恰关联2个4-顶点和1个3-顶点,则当f相邻一个 semi-bad-6-面时,由 R3和R4.2可知;当f相邻1个bad-6-面时,由 R3和 R4.2可知;否 则 由 R3和 R4.2可 知 ch*(f)≥ch(f)+× 3=0。

如果f恰关联1个4-顶点和2个3-顶点,则由引理8可知f至多相邻1个bad-6-面。当f相邻1个worst或 worse-6-面 时 ,由 R4.2可 知 ch*(f)≥;当 f相邻1个 bad-6-面,由 R3和R4.2可知;否 则由R3和R4.2可知。

如果f恰关联3个3-顶点,则由引理3可知f不能相邻于任何的worst-6-面。如果f相邻1个worse-6-面,则由R4.2和引理6可知ch*(f)≥ch(f)+×2=0;否则由R3和R4.2可知ch*(f)≥ch(f)+×3=0。

(2)d(f)=6。

如果f是一个非简单6-面,则由引理5(1)可知f不相邻于任何3-面,且由R1.2可知ch*(f)≥ch(f)-×4=>0。因此,在下面的讨论中假设f是1个简单6-面。由引理5(4)可知f至多相邻1个3-面。如果f不相邻于任何3-面,则由R1.2可知ch*(f)≥ch(f)-× 6=0。

如果 f是 light-6-面且相邻 1个 3-面,即 f是worst-6-面,则由引理6和引理7可知f至少相邻于2个11+-面且由R1和R3.1可知ch*(f)≥ch(f)-。

如果 f是 minimal-6-面且相邻 1个 3-面,即 f是worse-6-面或bad-6-面。因此,由R1和R3.2可知。

如果f恰关联2个4+-顶点且相邻1个3-面,则f是 semi-bad-6-面 或 good-6-面 。 由 R1、R3.3 和R3.4可知。

如果f至少关联3个4+-顶点且相邻1个3-面,则f是good-6-面。因此,由R1和R3.4可知ch*(f)≥。

(3)d(f)=7。

由引理5(2)可知f不相邻于任何3-面,且由R1.2可知。

(4)d(f)=9。

如果f是简单9-面,则由引理7可知f不相邻于任何3-面,因此由R1.2可知9=2>0。如果f是非简单9-面,即b(f)是由1个3-圈和6-圈或3个3-圈构成的,则f至多相邻1个3-面。因此,由R1和R4可知。

(5)d(f)=10。

由引理5(3)可知f至多非正规相邻1个3-面且由R1.2和R4可知。

(6)d(f)=11。

情形1:若f是 light-11-面,则f至多相邻5个 3-面。由引理3可知f不能相邻于任何的worst-6-面且每个相邻的3-面都是minimal-3-面。

如果f相邻于5个3-面,则由引理5(4)和引理6可知f至多相邻1个6-面g且g相邻1个3-面h。如果 h是 (3,3,5+)-面,则由 R1和 R4可知 ch*(f)≥。如果 h是(3,3,4)-面,则由引理 9可知 g不是 bad-6-面且由R1和R4.2可知。

如果f至多相邻于4个3-面,则由R1和R4可知。

注:对于11+-面f,在检验面f的权值时,可以将f关联的4+-顶点都看成4-顶点。这是因为:

1)将5+-顶点改成4-顶点,不减少f所相邻的3-面的个数,且不改变f的light性;

2)由权转移规则可知,f通过(k,5+)-边给相邻的3-面的权值为或,而 f通过(k,4)-边给相邻的3-面的权值为或。若 f通过(k,5+)-边给相邻的3-面g的权值为,则 f通过 (k,4)-边给相邻的 3-面g的权值不可能为,所以f给相邻的3-面的权值不会减少;

3)f给关联的3-顶点的权值不变;

4)将5+-顶点改成4-顶点,不减少f所相邻的worst-6-面的个数。

由注可知,只需考虑以下几种情形。

情形2:若f恰关联1个4-顶点u,则f至多相邻6个3-面。由引理3可知f至多需要给2个worst-6-面权值。

如果 f恰相邻 6个 3-面,则由引理 5(4)可知 f不能相邻于任何的6-面且4-顶点u也不关联任何的6-面。因此,由R1.1和R4.2可知ch*(f)≥ch(f)-。

如果f恰相邻5个3-面,当u关联2个3-面时,f至多相邻 2个 worst-6-面。此时,由 R1、R3.1和R4.2可知。如果u恰关联一个3-面,则f至多相邻1个worst-6-面和1个worse-6-面且该worse-6-面关联于 u。此时,由 R1、R3.1和 R4.2可知。如果u不关联任何3-面,则f至多相邻2个worse-6-面且这两个worse-6-面都关联于u。此时,由R1和R4.2可知。

如果f至多相邻4个3-面,则由R1、R3.1和R4.2可知。

情形3:若f恰关联2个4-顶点u和v,则f至多相邻6个3-面。由引理3可知f至多需要给4个worst-6-面权值。

如果f恰相邻6个3-面,则f关联1个rich-3-顶点或者4-顶点u关联1个3-面。如果f关联1个rich-3-顶点,则f至多相邻1个worst-6-面。因此,由R1、R3.1和R4.2可知。如果u关联1个3-面,则f至多相邻1个6-面且该6-面关联于u。因此,由R1、R3.1和 R4.2可 知。

如果f恰相邻5个3-面,则f至多关联3个rich-3-顶点。

如果uv∈E(G)且u和v都关联2个3-面,则f关联3个rich-3-顶点。因此,f至多相邻3个6-面且由R1、R3.1和 R4.2可知。 如 果uv∈E(G)且只有v关联2个3-面,则f至多相邻3个6-面且其中一个6-面关联u。因此,由R1、R3.1和R4.2可知。如果uv∈E(G)且u和v都恰关联一个3-面,则f关联一个rich-3-顶点。因此,f至多相邻1个6-面且每个关联于u或v的3-面都可以相邻于1个6-面。因此,由R1、R3.1和R4.2可知。因此,可以假设uv∈E(G)且关联于u或v的3-面的总个数至多为1。如果u和v恰关联同一个3-面,则f恰关联一个rich-3-顶点。因此,f至多相邻3个6-面且这些6-面都不是 worst-6-面 。因此,由 R1、R3.1和 R4.2可知。如果只有u关联1个3-面,则f不关联任何的rich-3-顶点。因此,f至多与1个关联v的6-面相邻于(3,4)-边,除此之外,关联于u的3-面可能相邻1个6-面,所以由R1、R3.1和R4.2可知。

如果uv∉E(G)且u和v都关联2个3-面,则f关联3个rich-3-顶点。因此,f至多相邻3个6-面且由R1、R3.1和R4.2可知。 如 果uv∉ E(G)且 v关联 2个 3-面,u关联 1个 3-面,则 f至多相邻3个6-面且其中1个6-面关联u。因此,由R1、R3.1和 R4.2可知。如果u不关联任何的3-面,则f关联一个rich-3-顶点。因此,f至多相邻1个worst-6-面和2个关联于u的6-面。因此,由R1、R3.1和R4.2可知。如果uv∉E(G)且u和v都恰关联1个3-面,则f关联 1个 rich-3-顶点。因此,f至多相邻1个worst-6-面和关联于 u或v的2个 6-面。因此,由 R1、R3.1和R4.2可 知。如果uv∉E(G)且只有v恰关联1个3-面,则f不关联任何rich-3-顶点。因此,f至多相邻3个6-面且这些6-面关联于u或v,由R1、R3.1和 R4.2可知。

如果f至多相邻4个3-面,则由R1、R3.1和R4.2可知4=0。

情形4:若f恰关联3个4-顶点,则f至多相邻7个3-面。如果 f恰相邻 7个 3-面,则由 R1、R3.1和R4.2可知。如果f至多相邻6个3-面且f相邻m个worst-6-面,则 f关联 m个 rich-3-顶点且由 R1、R3.1和R4.2可知。

情形5:如果f至少关联4个4-顶点,则由断言1可知ch*(f)≥ 0。

(7)d(f)=12。

若f是light-12-面,则f至多相邻6个3-面。由引理3可知f不能相邻于任何的worst-6-面且每个相邻的3-面都是minimal-3-面。如果f相邻于6个3-面,则由引理5(4)可知f不能相邻于任何的6-面。因此由R1和R4.2可知。如果f相邻5个3-面,则f关联2个rich-3-顶点。因此f至多相邻2个6-面且由R1和R4.2可知ch*(f)≥。如果f至多相邻4个3-面,则由R1和R4可知ch*(f)≥。

如果f恰关联一个4-顶点,则f至多相邻6个3-面。如果f恰相邻6个3-面,则由引理5(4)和引理6可知f至多相邻1个6-面。因此,由R1、R3.1和R4.2可知。如果f至多相邻5个3-面且f相邻m个worst-6-面,则 f关联 m 个 rich-3-顶点且由 R1、R3.1和 R4.2可 知。

如果f恰关联2个4-顶点,则f至多相邻7个3-面。如果f恰相邻7个3-面,则由引理5(4)可知f不相邻任何6-面。因此,由R1和R4.2可知ch*(f)≥。如果f至多相邻6个3-面且f相邻m个worst-6-面,则f关联m个rich-3-顶点且由R1、R3.1和R4.2可知ch*(f)≥ ch(f)-。

如果f至少关联3个4-顶点,则由断言1可知ch*(f)≥ 0。

(8)d(f)=13。

若f是light-13-面,则f至多相邻6个3-面。由引理3可知f不能相邻于任何的worst-6-面且每个相邻的3-面都是minimal-3-面。如果f相邻于6个3-面,则f恰关联一个rich-3-顶点且由引理5(4)可知f至多相邻1个6-面。因此由R1和R4.2可知ch*(f)≥。如果f至多相邻5个3-面,则由R1和R4可知ch*(f)≥。

如果f恰关联1个4-顶点,则f至多相邻7个3-面。如果f恰相邻7个3-面,则由引理5(4)可知f不能相邻于任何的6-面。因此,由R1.1和R4.2可知。如果f至多相邻6个3-面且f相邻m个worst-6-面,则f关联m个rich-3-顶点且由R1、R3.1和R4.2可知ch*(f)≥。

如果f至少关联2个4-顶点,则由断言1可知ch*(f)≥ 0。

(9)d(f)=14。

若f是light-14-面,则f至多相邻7个3-面。由引理3可知f不能相邻于任何的worst-6-面且每个相邻的3-面都是minimal-3-面。如果f相邻于7个3-面,则由引理5(4)可知f不相邻任何6-面。因此,由R1和R4.2可知。如果f至多相邻6个3-面,则由R1、R3.1和R4.2 可知。

如果f至少关联1个4-顶点,则由断言1可知ch*(f)≥ 0。

(10)d(f)=15。

若f是light-15-面,则f至多相邻7个3-面。由引理3可知f不能相邻于任何的worst-6-面且每个相邻的3-面都是minimal-3-面。因此,由R1和R4.2可知。

如果f至少关联1个4-顶点,则由断言1可知ch*(f)≥ 0。

参考文献

[1] VIZING V.Vertex colorings with given colors[J].Metody Diskret Analiz(Novosibirst),1976,29:3-10.

[2]ERDŐS P,RUBIN A,TAYLOR H.Choosability in graphs[C]//CHINN P,MCCARTHY D.Proceedings of the West Coast Conference on combinatorics,graph theory and computing.Arcata,California:Humboldt State University,1979(26):125-157.

[ 3] THOMASSEN C.Every planar graph is 5-choosable[J].Journal of Combinatorial Theory Series B,1994,62(1):180-181.

[4]THOMASSEN C.3-list-coloring planar graphs of girth 5[J].Journal of Combinatorial Theory Series B,1995,64(1):101-107.

[ 5] VOIGT M.List coloring of planar graphs[J].Discrete Mathematics,1993,120(1/2/3):215-219.

[6]VOIGT M,WIRTH B.A not 3-choosable planar graph without 3-cycles[J].Discrete Mathematics,1995,146(1/2/3):325-328.

[7]DVOŘÁK Z,POSTLE L.Correspondence coloring and its application to list-coloring planar graphs without cycles of length 4 to 8[J].Journal of Combinatorial Theory(Series B),2018,129:38-54.

[8]BERNSHTEYN A.The asymptotic behavior of the correspondence chromatic number [J]. Discrete Mathematics,2016,339(11):2680-2692.

[9] ALON N.Degrees and choice numbers[J].Random Structures&Algorithms,2000,16(4):364-368.

[10]BERNSHTEYN A,KOSTOCHKA A.Sharp dirac’s theorem for DP-critical graphs[J].Journal of Graph Theory,2018,88(3):521-546.

[11] BERNSHTEYN A,KOSTOCHKA A,PRON S.On DP-coloring of graphs and multigraphs [J].Siberian Mathematical Journal,2017,58(1):28-36.

[12]BERNSHTEYN A,KOSTOCHKA A,ZHU X.DP-colorings of graphs with high chromatic number[J].European Journal of Combinatorics,2017,65:122-129.

[13] CHEN L,LIU R,YU R,et al.DP-4-colorability of two classes of planar graphs[J].Discrete Mathematics,2019,342(11):2984-2993.

[14] KIM S J,OZEKI K.A sufficient condition for DP-4-colorability[J].Discrete Mathematics,2018,341(7):1983-1986.

[15]LIU R,LI X,NAKPRASIT K,et al.DP-4-colorability of two classes of planar graphs without adjacent cycles of given length[J].Discrete Applied Mathematics,2020,277:245-251.

[16]LIU R,LOEB S,ROLEK M,et al.DP-3-coloring of planar graphs without 4,9-cycles and cycles of two lengths from{6,7,8}[J].Graphs and Combinatorics,2019,35(3):695-705.

[17]LIU R,LOEB S,YIN Y,et al.DP-3-coloring of some planar graphs[J].Discrete Mathematics,2019,342(1):178-189.

[18]YIN Y,YU G.Planar graphs without cycles of lengths 4 and 5 and close trianglesare DP-3-colorable[J].Discrete Mathematics,2019,342(8):2333-2341.

[19] ZHANG H.A sufficient condition for a toroidal graph to be3-choosable[J].ArsCombinatoria,2012,105:193-203.

[20]WANG Y,WU Q.Planar graphs without cycles of length 4,5,8 or 10 are 3-choosable[J].Advances in Applied Mathematics,2011,10(3):297-305.

(责任编辑:马田田)