设为首页 加入收藏 期刊导航 网站地图
  • 首页
  • 期刊
    • 数学与物理
    • 地球与环境
    • 信息通讯
    • 经济与管理
    • 生命科学
    • 工程技术
    • 医药卫生
    • 人文社科
    • 化学与材料
  • 会议
  • 合作
  • 新闻
  • 我们
  • 招聘
  • 千人智库
  • 我要投稿
  • 办刊

期刊菜单

  • ●领域
  • ●编委
  • ●投稿须知
  • ●最新文章
  • ●检索
  • ●投稿

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematicsA^êÆ?Ð,2023,12(3),907-918
PublishedOnlineMarch2023inHans.https://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2023.123093
ع‰½•²¡ã
DP-/Ú
ëë먨¨]]]
úô“‰ŒÆ§êƆOŽÅ‰ÆÆ§úô7u
ÂvFϵ2023c211F¶¹^Fϵ2023c36F¶uÙFϵ2023c314F
Á‡
DP-/ÚVg•Ð^uy²Ø¹••48á²¡ã´3-LŒ/,¿…ù‡(Ø)û
Ü©Erd¨osJÑfzL/Ú‡Steinberg ߎÜ©‰Y,ƒ,DP-/ÚŠ•L
/Úí2,3/ÚïÄ¥É5õ'5.éuL/ÚïıYA›c,²¡ã
3-ŒÀÚ4-ŒÀ¯KÑáuNP-(J¯K,Äud,Cc·‚m©ïÄ3÷v®•,.
²¡ã´3-ŒÀ½4-ŒÀÄ:þ,&?Ù´Ä•DP-3-Œ /½DP-4-Œ/.3ùŸ©
Ùp§·‚y²¤ kع••4§5§7§10²¡ã´DP-3-Œ/,ÿÐDP-3-Œ/
ã‰Œ.
'…c
S-k-/Ú§DP-/Ú§²¡ã§=£
DP-ColoringofPlanarGraphwithout
GivenShortCycle
ZhongyongLian
CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang
Received:Feb.11
th
,2023;accepted:Mar.6
th
,2023;published:Mar.14
th
,2023
©ÙÚ^:ë¨].ع‰½•²¡ãDP-/Ú[J].A^êÆ?Ð,2023,12(3):907-918.
DOI:10.12677/aam.2023.123093
ë¨]
Abstract
TheconceptofDP-coloringwasinitiallyusedtoprovethataplanargraphwithout
cycleoflengthfrom4to8is3-list-coloring,andthisconclusionsolvesthepartial
problemsoftheSteinbergconjectureoftheweakenedlistcoloringversionproposed
byErd¨os.As ageneralization oflistcoloring, DP-coloring has received moreandmore
attention in the study of coloring.The research on list coloring has lasted for decades,
andthe3-choosableand4-choosableproblemsofplanargraphsbelongtoNP-difficult
problems.Basedonthis,inrecentyears,wehavebeguntostudywhetherplanar
graphs satisfyingsomeconfigurationsareDP-3-colorable orDP-4-colorable; moreover,
whethertheyareDP-3-colorableorDP-4-colorable.Inthisthesis,weprovethatall
planargraphswithoutcyclesoflength4,5,7,10areDP-3-colorable,whichextends
therangeofgraphsthatsatisfyDP-3-colorable.
Keywords
S-k-Coloring,DP-Coloring,PlanarGraph,Charge-Transfer
Copyright
c
2023byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.0
©¤•Äã´k•¿…{ü.XJ˜‡ãŒ±i\îAp²¡¥,@o¡§•˜
‡²¡ã.²¡ãn/Ú¯K´ã/ÚnØ¥˜‡-‡‘K.²;Gr¨otzsch½n[1] •Ñ:
Ãn/²¡ã´3ÚŒ/.ͶSteinbergߎ•µØ¹k••4½5 ²¡ã´3 ÚŒ/
.Tߎ˜†áÚX²¡ãn/Ú¯K2•ïÄ.-<¿´,Steinberg ߎ[2]Ccy
²Ø¤á.
ãDP-/Ú½Â(•¡•éA/Ú)´dDvoˇr´akÚPostleJÑ[3],¦‚^§5y²z
‡Ø¹•Ýl4 8 ²¡ã ´3-L-Œ/(=3-ŒÀ).8c§ãDP-/ÚŠ•˜‡Õá
/Ú‘KÉ5õïÄ'5.
ãDP-k-Œ/5ruãLk-Œ/5,Ïdég,/•Ä˜²;L3-/Ú½n£•
DOI:10.12677/aam.2023.123093908A^êÆ?Ð
ë¨]
?˜Ú§n/Ú½n¤UÄ\r•DP-3-Œ/.Erd¨os'uSteinbergߎfz¯KDP/Ú‡
QãXe:
¯K1.1¦•êk(k≥5),¦·K/¤kع•Ý•4k²¡ãÑ´
DP-3-Œ/0¤á?
©z[4]Ú[5](JÑL²þãk• 3¿…k≤9.´Äk≤8,=/¤kع•Ý•4
k²¡ãÑ´DP-3-Œ/0´Ä¤á§Eδ˜‡m˜5¯K.
/Ú¯Kþ®²鲡ã\þ˜3áþ•›DP-3-/ÚÜ©¤J.~X,
عƒn/•Ø¹••{4,5,6,7}[6]²¡ã´DP-3-Œ/;عƒn/•
ع••{5,6,9}Œ²¡ã´DP-3-Œ/;ع••{3,5,6}[5]½ö{3,6,7,8}[5]½ö
{4,5,6,9}[5]½ö{4,5,7,9}[5]½ö{4,6,8,9}[4]½ö{4,7,8,9}[4]•²¡ã´DP-3-Œ/
.
3©¥,·‚ïĘaعo«•Ý²¡ãDP-3-/Ú¯K.þã(Jy²˜
ع{4,i,j,9}•²¡ã´DP-3-Œ/,Ù¥4 <i<j<9.©•ÄXeaq¯K:
¯K1.2éu=êé(i,j),Ù¥4 <i<j<10,عk•áu{4,i,j,10}²¡ãÑ
´DP-3-Œ/?
8c•Ž,'uù‡¯K„vk®•(J.e¡½n´©̇(J,§y¢¯K
1.2˜‡œ¹.
½n1.3¤kع••4,5,7½10²¡ãÑ´DP-3-Œ/.
2.S-/ÚÄVg
½Â2.1bG´˜‡ã,S´˜êü¤8Ü.eD´G˜‡••§N
σ:E(D)→S©‰Dz^k•>e˜‡Spüσ
e
,KkSé(D,σ)¡ŠG˜
‡S-IP,σ¡ŠG˜‡ÎÒ˜,σ
e
¡ŠeÎÒ.(D,σ)•¡•˜‡S-IPã.N
f:V(G)→[k]={1,2...k}.eéuDz^k•>e=(x,y),kσ
e
(f(x))6=f(y),K¡f•
(D,σ) ˜‡k-/Ú.XJãGz˜‡S-IPãÑ´k-Œ/,@o¡G´S-k-Œ/.ãG
S-Úê´•÷vG´S-k-Œ/k•Š.
Jin!WongÚZhu[7]JÑãS-k-/ÚVg.§´Nõ-‡/ÚVgí2,•)k-/Ú!
ÎÒk-/Ú!ÎÒZ
k
-/Ú!DP-k-/Ú!+/ÚÚOÃã/Ú.AO/§XJSŠ•¤k ê
ü8ܧ@oS-k-/ÚduãDP-k-/Ú.
-S
k
L«8Ü[k]=1,2,...,kþ¤kü8Ü,-S
3
={id,(12),(13),(23),(123),(132)}§
Ù¥id•ðü.éu˜‡ãS-k-/Ú,duôÚ8´[k],¤±8ÜSŒ±•›3[k]þÜ©
ü.Ïd§DP-k-/ÚƒuS
k
-k-/Ú.Ïd,½n1.3Œ±-#LãXe.
½n2.1¤kع••4,5,7Ú10²¡ã´S
3
-3-Œ/.
DOI:10.12677/aam.2023.123093909A^êÆ?Ð
ë¨]
‰½˜‡S
k
-IPã(D,σ).^˜‡ÎÒs∈S
k
=†˜‡:u½Â,˜‡IÒσ
0
Xe:
σ
0
e
=









s◦σ
e
,ee= (u,v);
σ
e
◦s
−1
,ee= (v,u);
σ
e
,ÄK.
XJ˜‡S
k
-IP㌱l,˜‡S
k
-IPãÏL˜X=†§K¡ùü‡IPã´d=
†.w,,ü‡=†dS
k
-IPãäkƒÓS
k
-Úê.XJ˜^>ÎÒ•id,K¡§•>,
ÄK¡•K>.XJ˜‡¤k>Ñ´,@o¡§•.XJ˜‡Œ ±d =†•
,@o¡ù‡•;ÄK¡•K.
2.1.ÎÒ9Ù½Â
·‚PG•Ø¹••4,5,7,10ëϲ¡ã£‰½²¡i\¤8Ü.
½Â2.2-C•ãG∈G¥˜‡.XJCSÜ˜‡º:vkn‡:v
1
,v
2
,v
3
3Cþ,@
oG[{vv
1
,vv
2
,vv
3
}]¡•C˜‡9..XJ˜‡14
−
-vk9.,@o¡§•˜‡Ð¶ÄK¡§
•˜‡€.
˜‡C§9.¤y©¤z‡¡•¿.c
i
•˜‡¿•Ý.·‚?˜Ú¡ƒ
•(c
1
,c
2
,c
3
)-9..Xã1:
Figure1.(c
1
,c
2
,c
3
)-claw
ã1.(c
1
,c
2
,c
3
)-9.
Šâ€½Â,·‚Œ±éN´/ѱeÚn.
Ún2.2XJC´G¥ã˜‡€,@o|C|= 13§¿…Ck˜‡(3,8,8)-9..
!Ù{Ü©´½n2.1y²¤IÙ¦ÎÒ.
3˜‡²¡ãGþ,XJ˜‡º: uÃ.½¡>.þ,K·‚¡§•Ü;ÄK§´S
Ü.éu˜‡C,-int(C) Úext(C) ©OL«CSÜÚÜº:8Ü.XJ˜‡¡¤k
:Ñ´SÜ(Ü),@où‡·‚¡ù‡¡´SÜ(Ü).˜‡ CXJ÷vint(C) Ú
ext(C) Ñš˜,K·‚¡ù‡•©l.
DOI:10.12677/aam.2023.123093910A^êÆ?Ð
ë¨]
XJü‡¡kÓ>,K·‚¡§‚´ƒ.´»P½C•Ý,·‚^|P|½|C|L«,§
‚©O•P†C>ê.·‚^d(f)L«˜‡²¡ã¡fŒ.k•˜‡ê.k-º:(©O
/,k
+
-º:Úk
−
-º:)L«´˜‡÷vd(v) = kº:(©O/k,d(v) ≥kÚd(v) ≤k).ƒaq
VgA^u´»,Ú¡,Ù¥d(v)©O|P|,|C|Úd(f)“.XJv†P˜‡"àº:ƒ,
K·‚¡´»PÚ˜‡º:v∈V(P)ƒ.k-G´˜^•¹k‡2Ý:´»,¿…§†2Ý:؃
.d
1
,d
2
,d
3
´n‡ ê,§‚÷v3≤d
1
≤d
2
≤d
3
.˜‡(d
1
,d
2
,d
3
)-¡´˜‡•¹º:v
1
,v
2
,v
3
3-¡,Ù¥éuz˜‡i∈{1,2,3},v
i
´˜‡SÜ,Ý•d
i
:.
p=u
1
u
2
u
3
u
4
•²¡ã˜^´.XJp¤k:Ñ´Ý•3S:§¿…÷v±e^‡Ù¥
˜^,@o¡p´˜^д:
1.´»pØáu,‡¡>.§…>u
1
u
2
Úu
3
u
4
þ'阇n/[u
2
u
1
v] Ú[u
3
u
4
w].
2.´»páu,‡¡>.§…>u
1
u
2
'阇n/.
˜‡A-:´˜‡3-S:,¿…§áu˜‡SÜ3-¡;˜‡B-:´˜‡4-S:,¿…§Úü
‡3-¡ƒ';˜‡C-:´˜‡S:,¿…§QØ´A-:,•Ø´B-:;˜‡D-:´˜‡:,XJ§
Ú˜‡n/Tƒ',·‚òù‡:P•D
1
-:,AO/,XJn/Tk˜^ >3™.½¡>
.þ¿…§k˜‡3-S:,@o·‚¡n/T•AÏn/.
3.½n2.1y²
½n3.1-(D,σ)´˜‡ãG∈GS
3
-IPã.XJGÃ.½¡f
0
>.´‡Ð,@o(D[V(f
0
)],
σ)?¿3-/ÚŒ±òÿ(D,σ)§=Œ±*Ð(D,σ)˜‡3-/Ú.
l½n3.1Œ±íѽn2.1.b•3šS
3
-3-Œ/ãG∈G"Gkš3-Œ/S
3
-IÒ
ã(D,σ).·‚•Œ•–•5²¡ã´DP-3-Œ/,ÏdDk3-C.?C˜‡3-/Úφ.
dÚn2.2,·‚•C´Ð.@o,d½n3.1,·‚Œ±òφòÿ(ext(C),σ)Ú(int(C),σ).
·‚ò^‡y{5y²½n3.1.-G´½n3.1˜‡4‡~,§÷vσ(G)=|V(G)|+
|E(G)|•Š.·‚Œ±bf
0
>.U´˜‡Ð,φ
0
´(D[V(f
0
),σ])˜‡3-/Ú,´T/
ÚØUòÿ‡(D,σ).
3.1.(5Ÿ
Ún3.2Gع©lÐ.
y²:XJC´G©lÐ,@od(D,σ)45,·‚Œ±òφ
0
òÿ (D−int(C),σ),
,òC/Úòÿ(int(C),σ).ùφ
0
Òòÿ‡(D,σ)þ,ù†·‚bgñ.
Ún3.3G´ëÏ.
y²:ÄK,·‚Œ±bDk˜‡¬BÚ˜‡•:v∈V(B).ÏL(D,σ)45,·‚Œ
±òφ
0
òÿ(D−V(B−v),σ).-f•B•¹:v˜‡¡,¿…d(f)•Š. XJd(f) ≤12,
@odÚn2.2,·‚Œ±íäÑf>.´˜‡Ð.Ïd,d(D,σ)45§v/ÚŒòÿ
DOI:10.12677/aam.2023.123093911A^êÆ?Ð
ë¨]
(f,σ),¿?˜Úòÿ(B,σ).d,XJd(f)≥13,@ov3f>.þü‡:ƒm\˜
^fSÜk•>e,˜‡3-¡T.w,§B+e∈G.aq,d(D,σ)45,·‚Œ±
òÿv/Ú(T,σ)¿…?˜Úòÿ(B+e,σ)þ.3þãü«œ¹e,(D,σ)•ª/ÚÑ´
dφ
0
òÿ,ù†·‚½nbgñ.
Ún3.4GS:Ý–•3.
y²:XJG¥•3˜‡Ý•p•2S:v,@o·‚Œ±ÏL(D,σ)45òφ
0
òÿ
(D−v,σ),¿…éw,Œ±?˜Úòÿ(D,σ).
53.5XJ(D,σ
0
)´˜‡S
3
-IPã,¿…§=†du(D,σ),@o(D,σ
0
)•´½n3.1˜‡
4‡~.
Ún3.6(D,σ)عK(3,3,3)-¡.
y²:bTÚnؤá,v
1
v
2
v
3
´˜‡3G¥K(3,3,3)-¡,¿…éui∈[3],
u
i
∈N(v
i
)¿…u
i
6= v
i
.d53.5§·‚Œ±bu
1
v
1
v
2
u
2
Úv
1
v
3
u
3
>þ•.dK¿,v
2
v
3
•K>.du(D,σ) 45,(D−{v
1
,v
2
,v
3
},σ) k˜‡3-/Úφ,@o·‚Œ±ÏL±e•ªò
/Úφ
0
òÿG.
e∃i∈{2,3},φ
0
(u
1
) 6=φ
0
(u
i
),Ø”˜„5,i= 2,@o·‚^ôÚφ
0
(u
1
) /v
2
,X ·
‚2Uìv
3
→v
1
^Sò•e:/Ð,K‡ãGÒ/Ð.¤±,φ
0
(u
1
),φ
0
(u
2
),φ
0
(u
3
) 7/
Ó˜ôÚ,Ø”•ôÚ1.Ï•v
2
v
3
•K >,¤±Ùüà:ôÚÓž/¤2 ½öÓž/¤3,7k
˜«œ¹†T>ÎÒØÀâ.•,v
1
„k˜‡Œ^ôÚ.
Ún3.7éu?¿‰½÷v3≤k≤14êkÚ÷vt≥b
k−1
2
cêt,ãG?¿k-¡(f
0
Ø
)>.ÑØ•¹t-G.
y²:‡y{.bGk˜‡¡f,§>.C•¹˜‡t-GL.-D
0
=D−V(L)¿
…U
0
=U∪C−V(L).·‚Äkòφ
0
òÿU∪C.·‚5¿U
0
´D
0
pÃ.½¡>.,¿
…|D
0
|= |D|−|V(L)|+(|C|−2−|V(L)|) ≤|D|+k−2−2b
k−1
2
c≤|D|.Ïd,U
0
/ÚŒ±
òÿ(D
0
,σ).ù†·‚bφ
0
ØUòÿ(D,σ)gñ.
Ún3.8(D,σ)Ø•¹ü‡ƒ(3,3,4)-¡.
y²:ÄK,·‚[uvw]Ú[wxy]´ƒu:w?ü‡(3,3,4)-¡.duGعk4,¤±
ùü‡3-¡Øƒ,Ïd,w7½´Ý•4:.u
0
,v
0
,x
0
,y
0
©O´u,v,x,y•e@‡:(=Ø
3ùü‡3-¡þ:).ÏL53.5,·‚Œ±ÀJ(D,σ)§¦u
0
uwvv
0
Úx
0
xwyy
0
þ>Ñ•
.·‚Ø”bu
0
,x
0
Ø•¹3Ó˜‡¡þ.ÏLl(D,σ)¥íØ:u,v,w,x,y¿…ò:u
0
†:x
0
?
1˜‡Ê:öŠ,·‚˜‡#ã(D
0
,σ
0
).PD
0
.ã•G
0
.·‚òy²/Úφ
0
Œ±òÿ
(D
0
,σ
0
)þ,=÷v½n8B^‡.
Äk§I‡yþããöŠØ¬)#k-(k≤10)§G
0
∈G.XJ)˜‡#k-,@
où‡k-éA´ãGp˜^u
0
Úx
0
ƒmk-´»,§†´»u
0
uwxx
0
|Ü/¤˜‡(k+4)-,
·‚Pù‡•C.Šâã²¡5,:vÚ:yÙ¥˜‡ uCS,,˜‡ uC.Ïd,C´˜‡
©lÐ,ù†Ún3.2ƒgñ.
DOI:10.12677/aam.2023.123093912A^êÆ?Ð
ë¨]
Ùg§I‡y/Úφ
0
3D
0
¥E~.éuþããöŠ,•IüØü«œ¹µ1¤:u
0
Úx
0
þ
´G:;2¤u
0
Úx
0
Ù¥˜‡•:§…,˜‡•S:k˜‡:•:.éuœ¹1§
Uu
0
,x
0
y©¤ü^´»P
1
ÚP
2
.du|V(f
0
)|≤14§@oP
1
½öP
2
¥˜^´†´»u
0
uwxx
0
ƒ
(Ü´˜‡11
−
-.w,§T´Ð…©l:vÚ:y,ù†Ún3.2ƒgñ.éuœ¹2§Ø”b
u
0
´G˜‡S:.Pu
00
´u
0
˜‡3Uþ:.5¿u
00
,x
0
∈V(U),ÏLaquœ¹1?Ø
Œgñ"
·‚„I‡y´U´G
0
˜‡Ð.b†ƒƒ‡/,U´G
0
˜‡€,•Ò´`,U•
¹˜‡9.,P•H.Ï•G
0
∈G,dÚn2.2§H•U(3,8,8)-9.Pt•ÊÜu
0
Úx
0
:"
Ï•u
0
Úx
0
ØÓž•:,t3Hþ,@o†t'éHü‡¿þ•#)"w,,ùü‡¿–
k˜‡••8,=þããöŠ#)˜‡8-,gñ"
d(D,σ)45, φ
0
Œòÿ(D
0
,σ
0
)¿…XeöŠé•{:/Ú,•?˜Ú/òÿ(D,σ)þ:
ò:w/þÚ:u
0
ÓôÚ,@o·‚Œ±ò:vÚu•g/Ð,:yÚx•Œ•g/Ð.
·‚Ñ(Øφ
0
Œ±òÿ‡(D,σ),ù†·‚bgñ.
Ún3.9GØ•¹Ð´.
y²:‡y.bGk˜^дp= u
1
u
2
u
3
u
4
.
œ¹1:>u
1
u
2
Úu
3
u
4
©O•¹un/[u
2
u
1
v]†[u
3
u
4
w]¥.
-u
0
Úu
5
©O•u
1
Úu
4
u(:.ÏL=†,·‚Œ±ÀJ†:u
1
,u
2
,u
3
½u
4
ƒ'é
>þ•>.X,·‚ípþ¤k:¿…3u
0
Úu
5
ƒmV\˜^>.ùl(D,σ)˜
‡ #S
3
-IÒ²¡ã§PŠ(D
0
,σ
0
).·‚òy²/Úφ
0
Œ ±òÿ(D
0
,σ
0
)þ,=÷v½n8B
^‡.
Äk§yþããöŠØ¬)#k-(k≤10),D
0
∈G.ÄK,òTk-þ>u
0
u
5
^´
»u
0
u
1
..u
5
O†Œ±˜‡(k+4)-§PŠC.ùp‡5¿´:v,wØŒU´Cþ:.ÄK
{,Ø”b v∈V(C),@oCü‡uvu
1
Úvu
2
òCy©¤˜‡3-Ú˜‡11
+
-±9˜
‡8
+
-,ù†¯¢|C|≤14gñ.Ïd§éu:vÚw§˜‡ uCSÜ,,˜‡ uC
Ü.C´˜‡©lÐ,gñ.
Ùg§y/Úφ
0
3D
0
¥E~.éuþããöŠ,•Iy:u
0
Úu
5
Øþ´G:.ÄK§
u
0
Úu
5
òUy©¤ü^´»P
1
ÚP
2
.o• 3Ù¥˜^´»Ú#>u
0
u
5
|¤˜‡8
−
-§T´#
)§gñ.
•§yU3D
0
¥•´Ð.‡y,-H´D
0
¥U˜‡9..duDvk9.,N´í
Ñu
0
,u
5
Ú9.k'.Ïd·‚Ø”bu
0
´˜‡S:¿…u
0
kn‡3Uþ:,Ù¥•)u
5
.
Pu
0
,u
00
•,ü‡:.du|V(U)|≤14,@ou
0
,u
00
,u
5
òV(U)©¤n^´»,Ù¥–k˜^
±u
5
•à:´»Ù•Ý–õ•8.þããöŠò)˜‡#9
−
-,gñ.
duG45,/Úφ
0
Œ±òÿ(G
0
,σ
0
),¿ÏLXe/Ú?˜Úòÿ(G,σ):Pφ•G
0

/Ú.XJφ(u
0
)6=φ(v)¿…φ(u
5
)6=φ(w),@o·‚òu
0
ôÚ/‰u
2
§u
5
ôÚ/‰u
3
.@
oe5u
1
Úu
4
•w ,Œ±/Ð.XJφ(u
0
)=φ(v),@ow,Œ±Uu
4
,u
3
,u
2
,u
1
^ Sò/Úò
DOI:10.12677/aam.2023.123093913A^êÆ?Ð
ë¨]
ÿGþ.XJφ(u
5
) = φ(w),@ow,Œ±Uu
1
,u
2
,u
3
,u
4
^Sò/ÚòÿGþ.
œ¹2:´»p3˜‡¡>.þ,¿…>u
1
u
2
'阇n/[u
2
u
1
v].
-u
0
Úw©OL«u
1
Úu
3
u(Ø.ÏL=†,·‚Œ±ÀJãG, ¦ãG>u
3
w±
9†:u
1
,u
2
ƒ'é>Ñ•.X·‚lG¥íØ´»p¤kº:¿…ò:u
0
Ú:w?1Ê
:.ùl(D,σ)˜‡#S
3
-IÒ²¡ã,PŠ(D
0
,σ
0
).
Äk,yþããöŠØ¬)#•k-(k≤10),D
0
∈G.ÄK,k-éA ãD¥´
˜^k-´»,¿…§†´»u
0
u
1
u
2
u
3
w˜å|¤˜‡(k+4)- ,·‚-ù‡•C,Úœ¹1
yL§˜,C´˜‡Ð©l,ù´gñ.ÓÚœ¹1 ƒq/,·‚Œ±íÑu
0
ÚwØ
UӞѕãG:,¿…·‚öŠØ¬—ü‡:ƒ.ù`²/Úφ
0
3D
0
¥E~.
X,yU3D
0
¥•´Ð.‡y,-H´D
0
¥U˜‡9..duDvk9.,N´í
Ñu
0
,wÚ9.k'.@od9.½Â,Ù¥˜‡:,Ø”-T:•u
0
,u
0
kü‡:{u
0
,u
00
}
3V(U)þ,:wKk˜‡:w
0
,w
0
∈V(U).du|V(U)|≤14,@ou
0
,u
00
,w
0
òV(U)©¤n^
´»,Ù¥lu
0
–k˜^±w
0
•à:´»Ù•Ý–õ•8.þããöŠò)˜‡#9
−
-,g
ñ.Ïd·‚Œ±bw∈V(U) u
0
/∈V(U),@o:u
0
ŒUÒk ˜‡:u
0
,¿…u
0
kü‡
:{u
x
,u
y
}3V(U)þ.Óþ,·‚Œ±é˜‡#9
−
,gñ.
duG45,/Úφ
0
Œ±òÿ(G
0
,σ
0
),¿Ï LXe/Ú?˜Úòÿ(G,σ):Pφ•
G
0
/Ú.·‚•u
3
ØŒ±/ôÚφ(u
0
),eφ(v)6=φ(u
0
),@o·‚Œ±òu
0
ôÚ/
u
2
,e5u
1
•Œ±/Ð.eφ(v) =φ(u
0
),@o·‚Œ±U^Sòu
3
,u
2
,u
1
^Sò/Úòÿ
Gþ.
4.ãG=£
·‚ò(3,3,3)-¡L«•€n/;3-¡TЕ ¹ü‡3-S:,·‚ò§PŠgn/;3-¡•k
˜‡3-S:,·‚ò§PŠÊÏn/.Ù¦3-¡PŠÐn/"
e¡,·‚-V,EÚF©O•Gº:,>Ú¡8Ü.éuz‡x∈V∪F,xЩŠch(x)½
ÂXe:
ch(x) =









2d(x)−6,ex∈V;
d(x)−6,ex∈F\{f
0
};
d(x)+6,ex= f
0
.
(1)
|^ª
P
v ∈V(G)
d(v) = 2|E(G)|=
P
f∈F(G)
d(f)±9î.úª|V(G)|−|E(G)|+|F(G)|= 2,·
‚Œ±
X
x∈V(G)∪F(G)
ch(x) = 0.
X,·‚òé¤ kx∈V(G)∪F(G)ƒ½·=£5K?1=£5 ˜‡•ª
Šch
∗
(x)¿…·‚kch
∗
(x)>0.du3=£L§¥oŠ´Ø¬UC,ù‡=(J
DOI:10.12677/aam.2023.123093914A^êÆ?Ð
ë¨]
†·‚oЩŠ´gñ.
Šâ±e5K3V∪Fƒƒm?1=:
R1.f
0
=Ñ
10
7
‡z‡f
0
þ:v.
R2.éu6
+
-¡f,Ù¥f6= f
0
,f=Ñ
d(f)−6
d(f)
‡z‡¡þ:.
R3.-L•14
−
-¡f>.þ˜‡G,Ù¥f 6=f
0
.XJ:u´˜‡L:,@ou=
Ñ
42−3d(f)
14d(f)
‡z‡L:þ.
R4.-u•€n/þ˜‡º:,v•u3n/˜‡:,v=Ñ
1
2
‡u.
R5.(1)B-:=Ñ
35
22
‡z‡ƒ'gn/þ,ÄK=Ñ
29
22
‡z‡Ù¦an/þ.
(2)D-,C-:=Ñ2‡z‡ƒ'gn/þ.½ö=Ñ
35
22
‡z‡ÊÏn/þ,ÄK
=Ñ1‡z‡Ù¦an/þ(þãn/Ø•)AÏn/).
(3)D
1
-:=Ñ
57
44
‡z˜‡AÏn/þ,Ù¥TAÏn/k˜‡€n/n
ÝS:,ÄK=Ñ
19
14
‡z‡AÏn/þ.
3=£ƒ, ·‚o´rS3-:¤kŠ=†ƒƒ'én/þ.éuz‡x∈V∪F,
·‚Pch
∗
(x)•Ù²L=•ªŠ.
5Ÿ4.1é¤kSÜ3-¡f,ch
∗
(f) ≥0.
y²:Äk,·‚b[uvw]´˜‡€n/.XJ[uvw]†Ù¦3-¡Ø,@o[uvw]ŒU
Ú†8-¡ƒ, ÄK, [uvw]•UÚ11
+
-¡ƒ.dR4ÚR2,·‚kch
∗
(f) ≥ch(x)+3·
1
2
+3·2·
1
4
= 0.
XJ[uvw]´˜‡gn/¿…d(w)≥4,@oÏLÚn3.9,·‚•{u,v}؆€n/ƒ
.·‚•ÄwŒU´˜‡B-:œ¹,@oduãGعk10-¡,¤±[uvw]†–ü‡11
+
-¡ƒ
'.ÏLR2ÚR5(1),·‚kch
∗
(f)≥ch(f) + 2·(
5
11
+
1
4
) +
35
22
=−3 +
31
22
+
35
22
=0.XJw´˜
‡C-:½öD-:,@odR5(2),·‚kch
∗
(f) ≥ch(f)+2·2·
1
4
+2 = 0.
XJ[uvw]´˜‡ÊÏn/,@o•Ò´`,·‚Œ±bd(u)≥4,d(w)≥4.·‚•
vŒU†€n/ƒ,XJu½öw´B-:,@ovÚ11
+
-¡´ƒ'.XJu,wÑ´
B-:,@odR2,R4ÚR5(1),·‚kch
∗
(f)≥ch(f) −
1
2
+ 2
5
11
+ 2
29
22
=−3 −
1
2
+
39
11
=
1
22
.X
Ju´C-:,w´˜‡B-:,¿…v˜‡€n/,·‚Œ±íäÑv†ü‡11
+
-¡ƒ',@
och
∗
(f) ≥ch(f)−
1
2
+2
5
11
+
29
22
+
35
22
= −3−
1
2
+
10
11
+
64
22
>0.XJv؆€n/ƒ,džvŒ
U•Ú˜‡11
+
-¡k',@o·‚kch
∗
(f) ≥ch(f)+(
1
4
+
5
11
)+
29
22
+
35
22
>0.Ïd,·‚Œ±b
u,wÑ´C-:,XJv†€n/ƒ,@o·‚kch
∗
(f) ≥ch(f)+2
5
11
+
35
22
+
35
22
−
1
2
>0.X
Jv؆€n/ƒ,@o·‚kch
∗
(f) ≥ch(f)+2
1
4
+
35
22
+
35
22
>0.
XJ[uvw] ´˜‡Ðn/,@odR4,R5(2),·‚kch
∗
(f) ≥ch(f)+3·1 = 0.
5Ÿ4.2¤kB-,C-:v,ch
∗
(v) ≥0.
y²:v´˜‡B-:,@odÚn3.8,v•õ†˜‡gn/ƒ',ÏddR2ÚR5(1),
ch
∗
(v) ≥ch(v)+2
5
11
−
35
22
−
29
22
= 0.
DOI:10.12677/aam.2023.123093915A^êÆ?Ð
ë¨]
X·‚-v´˜‡C-:.XJd(v)=3,@oŠâ½Â,vØ•¹3SÜn/¥.Ï
d,vŒUÚn‡6
+
-¡ƒ'.ŠâÚn3.9,v•õ˜‡€n/.XJv†€n/ƒ
,dãG∈G,@o·‚Œ±íäÑvŒU†ü‡8
+
-¡±9˜‡6
+
-¡ƒ',ÏddR2ÚR4,·
‚kch
∗
(v)≥ch(v)+2
1
4
+ 0−
1
2
=0.XJv؆€n/ƒ,@ovŒU†n‡6
+
-¡ƒ
',Ïd,ch
∗
(v)≥ch(v) + 3 ·0=0.XJv•¹u˜‡AÏn/¥,KŠâR2,R5(2),·‚
kch
∗
(v) ≥ch(v)+2·
1
4
>0½öch
∗
(v) ≥ch(v)+2·
5
11
−
1
2
>0.
XJd(v) ≥4,@o·‚-x••¹:vn/ê8,y•Úvƒ€n/ê8.·‚
•x≤b
d(v)
2
c¿…y≤d(v)−2x.XJv†˜‡€n/ƒ,@ov–Úü‡8
+
-¡ƒ',ÄK
ŒUÚü‡6
+
-¡ƒ'.Ïd,·‚Ø”•Äx‡ƒ'n/Ñ´gn/œ¹,džn/¤I
‡ŠÒ´•õ.dR2ÚR5(2),·‚kch
∗
(v) ≥ch(v)−x·2−y·
1
2
≥
3
2
·d(v)−6−b
d(v )
2
c.X
Jd(v) ≥6,@oÏLOŽ·‚kch
∗
(v) >0.
·‚E,I‡y4≤d(v)≤5žŠœ¹.XJd(v)=4,duv´C-:,@oŠâC-:
½Â,v•õÚ˜‡n/ƒ'.x=1,y=2ž,@ov†n‡11
+
-¡ƒ';x=1,y=1
ž,@ov†˜‡11
+
-¡±9ü‡8
+
-¡ƒ';x=1,y=0ž,@o†ü‡8
+
-¡±9˜‡6
+
-¡ƒ
';d,·‚„I‡•Äx=0,y≤4œ¹.Xþã¤kœ¹,·‚kch
∗
(x)≥{
4
11
,
5
11
,
1
2
,0}.
d(v) = 5,ÚÝ•o:äaq,§éN´y²ch
∗
(v) ≥0,·‚ÑùÜ©y².
5Ÿ4.3-v•>.f
0
þ˜‡:.@och
∗
(v) ≥0.
y²:XJd(v) = 2,@odR1,R2ÚR3,ch
∗
(v) ≥ch(v)+
10
7
+
d(f)−6
d(f)
+2·
42−3d(f)
14d(f)
= 0.
·‚bd(v)=3¿…†:vƒ'¡f,Ù¥f6=f
0
.XJd(f)=6,@odÚn3.6,·‚•
f•õ•k˜‡Ý:,KdR2ÚR3,v=
42−3d(f)
14d(f)
=
2
7
‡fÝ:þ.XJv´˜‡D-:
¿…d(f)=8,@ov=–
9
28
−
1
4
=
1
14
‡fÝ:þ.XJv´˜‡D-:¿…d(f)=11,@
ov–
5
11
−4·
42−3·11
154
=
17
77
‡.
œ¹1::v†˜‡6-¡ƒ'.
du ãGvk7-,10-,ÏdvØ•¹un/p,•Ø†n/ƒ,…,v•õ•áu ˜
‡6-.ÏLþ¡©Û,·‚kch
∗
(v) ≥ch(v)+
10
7
−
1
14
−
2
7
=
15
14
.
œ¹2:v´˜‡D
1
-:.
Ï•v´n/˜‡:,¤±v•ŒUÚ8
+
-ƒ'.dR1,R5(3)±9þ¡©Û,·‚
kch
∗
(v) ≥ch(v)+
10
7
−
1
14
−
19
14
= 0½öch
∗
(v) ≥ch(v)+
10
7
+
17
77
−
57
44
>0.
XJd(v)≥4,@o·‚Œ±bv†x‡n/ƒ'¿…y‡€n/.·‚Œ±í
äÑx≤b
d(v )
2
c¿…y≤d(v) −2x.dR1,R2ÚR5,d(v)≥5,x‡n/•gn/ž,·‚
kch
∗
(v) ≥2d(v)−6−x·2−y·
1
2
+
10
7
>0.XJd(v) = 4,@oŠâ=£5K,·‚•v†gn
/ƒ'ž›”•õŠ.Ïd,ch
∗
(v) ≥ch(v)−2+
10
7
−2·
1
14
>0.
5Ÿ4.4éu¤k†f
0
ƒ'én/,ch
∗
(f) ≥0.
y²:-[uvw]•˜‡AÏn/.
XJ[uvw]:u´˜‡nÝS:,¿…u؆n/ƒ.@odR2,R5,·‚kch
∗
(f)≥
DOI:10.12677/aam.2023.123093916A^êÆ?Ð
ë¨]
ch(f)+2·
19
14
+2·
1
4
= −3+
19
7
+
1
2
=
3
14
>0.
·‚Œ±bu˜‡€n/.@odR2,R4ÚR5(3),·‚ch
∗
(f)≥ch(f) +2·
57
44
+2·
5
11
−
1
2
= −3+
57
22
+
10
11
−
1
2
= 0.
-[uvw] •˜‡•¹k(ƒ˜‡:n/.
XJ[uvw] ´˜‡gn/,@odÚn3.9 ·‚•[uvw] S:ØŒU€n/,Ä
K·‚Œ±3G¥é˜^д,¤±dR2,R5(2)·‚kch
∗
(f)≥ch(f) + 2+ 4 ·
1
4
=0.X
J[uvw]´ÊÏn/,@od½Â·‚•[uvw]kü‡4
+
-:.e[uvw]˜‡€n
/,dR2,R4,R5 ·‚kch
∗
(f)≥ch(f) +2 ·
35
22
−
1
2
+2·
5
11
>0.e[uvw] Ø˜‡€n
/,dR2,R5 ·‚kch
∗
(f)≥ch(f) +2 ·
35
22
+ 2
1
4
>0.e[uvw] ´˜‡Ðn/,dR5 ·‚k
ch
∗
(f) ≥ch(f)+1+1+1 = 0.
5Ÿ4.5éu¤k4
+
-¡f,ch
∗
(f) ≥0.
y²:éuf6=f
0
,Ï•Gعk4−,5−,7−,10−,¤±f–•6
+
-¡,dR2,´•
ch
∗
(f) ≥0.f= f
0
ž,dR1Œ•ch
∗
(f) ≥ch(f)−
10
7
·d(f) ≥0.
nþ¤ã,·‚5ych
∗
(x) >0.·‚•ãG>.þ–k˜‡3
+
-:v,¿…d5Ÿ4.3
y²L§¥Œ±Ñv7L´˜‡D
1
-:¿…v3˜‡8-þ.·‚-†vk'n/•[uvw],Ù
¥u´G˜‡S:.(5¿[uvw]¥7k˜‡S:,ÄKãG¬ku•3,ù†Ún3.7´gñ.)d
un/†˜‡8-ƒ,¤±uØŒU´B-:.=´`u´˜‡C-:.qd5Ÿ4.2y²L§¥,
·‚•d(u)=4½öd(u) = 5.éuùü«œ¹Ódun/˜‡8-,·‚Œ±
Ñch
∗
(u) >0.ù·‚(ܱþ5Ÿ¤(Ø
P
x∈V∪F
ch
∗
(x) ≥0 Œ±ÑãG•ªŠƒÚ
Œu",y..
·‚éL/Ú˜®k(Ø?1²¡ãDP-/Úþí2.H.Zhang[8]32012cžy
² عk{4,5,7,10}•²¡ã´3-ŒÀ,ùŸ©Ù¥|^4‡~5Ÿ±9AO
/Ú\9.VgŠ•8B^‡íäÑã˜(,¿…|^=£•{éã?1©Û
Øy,y²عk{4,5,7,10}•²¡ã ´DP-3-Œ/.d,éuL/ÚãïÄ,
Y.Wang,H.LuÚM.Chen[9]u2010cy²عk{4,5,8,9}•²¡ã´3-ŒÀ,´
Äù‡(JUí2DP-3-Œ/,ù‡¯KX8„v‰Y,·‚ŒUI‡•Ä˜#8B^‡
y.
ë•©z
[1]Gr¨otzsch,H.(1959)EinDreifarbensatzf¨urdreikreisfreieNetzeaufderKugel.
WissenschaftlicheZeitschriftderMartin-Luther-Universit¨atHalle-Wittenberg,Math.-
NaturwissenschaftlicheReihe,8,109-120.
[2]Cohen-Addad, V.,Hebdige,M.,Kr´al,D.,Li,Z.and Salgado,E.(2017) Steinberg’sConjecture
IsFalse.JournalofCombinatorialTheory,SeriesB,122,452-456.
https://doi.org/10.1016/j.jctb.2016.07.006
DOI:10.12677/aam.2023.123093917A^êÆ?Ð
ë¨]
[3]Dvoˇr´ak, Z.and Postle, L. (2018) Correspondence Coloringand ItsApplicationto List-Coloring
PlanarGraphswithoutCyclesofLengths4to8.JournalofCombinatorialTheory,SeriesB,
129,38-54.https://doi.org/10.1016/j.jctb.2017.09.001
[4]Liu,R.,Loeb,S.,Rolek,M.,Yin,Y.andYu,G.(2019)DP-3-ColoringofPlanarGraphs
without4,9-CyclesandCyclesofTwoLengthsfrom6,7,8.GraphsandCombinatorics,35,
695-705.https://doi.org/10.1007/s00373-019-02025-2
[5]Liu,R.,Loeb,S.,Yin,Y.andYu,G.(2019)DP-3-ColoringofSomePlanarGraphs.Discrete
Mathematics,342,178-189.https://doi.org/10.1016/j.disc.2018.09.025
[6]Lv,J.(2022)PlanarGraphswithoutCyclesofLengthfrom4to7andIntersectingTriangles
AreDP-3-Colorable.GraphsandCombinatorics,38,ArticleNo.8.
https://doi.org/10.1007/s00373-021-02407-5
[7]Jin, L.,Wong, T.andZhu,X.(2021)Colouring ofS-LabelledPlanar Graphs.EuropeanJournal
ofCombinatorics,92,ArticleID:103198.https://doi.org/10.1016/j.ejc.2020.103198
[8]Zhang,H. (2012)ASufficientConditionforaToroidalGraphtoBe3-Choosable.ArsCombi-
natoria,105,193-203.
[9]Wang, Y., Lu, H.and Chen, M.(2010) PlanarGraphs withoutCycles ofLength 4, 5, 8or 9Are
3-Choosable.DiscreteMathematics,310,147-158.https://doi.org/10.1016/j.disc.2009.08.005
DOI:10.12677/aam.2023.123093918A^êÆ?Ð

版权所有：汉斯出版社 (Hans Publishers) Copyright © 2023 Hans Publishers Inc. All rights reserved.