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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematicsA^êÆ?Ð,2022,11(7),4760-4773
PublishedOnlineJuly2022inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2022.117501
²¡ãÚعK
5
-fªãfòzÝ
¶¶¶——————
úô“‰ŒÆ§êƆOŽÅ‰ÆÆ§úô7u
ÂvFϵ2022c619F¶¹^Fϵ2022c714F¶uÙFϵ2022c721F
Á‡
ãfòzÝ´dBernshteynÚLeeJÑ˜‡#½Â§´ãòzÝC/"Šâ½ÂŒ
•§z‡d-òzã•´d-fòz",˜•¡§XJG´fòz§@oχ(G)≤χ
l
(G)≤
χ
DP
(G)≤d+1"3ùŸØ©¥§·‚y²عK
5
-fªã´4-fòz¶Ø¹4-²¡
ã´3-fòz¶Ø¹4-†3-ƒ²¡ã´3-fòz"
'…c
òzݧfòzݧ²¡ã§•§=£
WeakDegeneracyofPlanarGraphsand
K
5
-Minor-FreeGraphs
XiaoxiaoDing
CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang
Received:Jun.19
th
,2021;accepted:Jul.14
th
,2022;published:Jul.21
st
,2022
Abstract
WeakdegeneracyofgraphsisanewdefinitionproposedbyBernshteynandLee.It
©ÙÚ^:¶——.²¡ãÚعK
5
-fªãfòzÝ[J].A^êÆ?Ð,2022,11(7):4760-4773.
DOI:10.12677/aam.2022.117501
¶——
isthedeformationofthedegeneracyofgraphs.Bydefinition,everyd-degenerate
graphisalsoweaklyd-degenerate.Ontheotherhand,ifGisweaklyd-degenerate,
thenχ(G)≤χ
l
(G)≤χ
DP
(G)≤d+1.Inthispaper,weprovethatplanargraphswith
K
5
-minor-freeareweakly4-degenerate,planargraphswithout4-cyclesareweakly
3-degenerateandplanargraphswithout4-cyclesadjacentto3-cyclesareweakly3-
degenerate.
Keywords
Degeneracy,WeakDegeneracy,PlanarGraphs,TheLengthofCycles,Discharging
Copyright
c
2022byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.Úó
Ÿ©Ù¥¤kãÑ´k•{üã.G˜‡kº:/Ú´•k«ôÚ1,2,...,kéuG
ˆº:˜‡©;XJ?¿ü‡ƒº:Ñ©ØÓôÚ,@o·‚¡T/Ú´~.
Gk˜‡~kº:/Úž,Ò¡G´kŒ/.ãGÚêχ(G)´•GŒ/êk•Š.
L/Ú´ãº:/Ú˜«í2.1976c,Vizing[1]Äg0ãL/ÚVg,1979
c,Erd˝os,Rubin±9Taylor[2]JÑ¿í2ãL/ÚVg.
‰ãGz˜‡º:v•½˜‡ôÚLL(v).XJéz˜‡º:v∈V(G),Ñ•3˜‡ô
Úϕ(v) ∈L(v),¦xy∈V(G)ž,ϕ(x) 6= ϕ(y),@o·‚¡G´L-Œ/.XJé?¿•½
ôÚLL,¦éz‡v∈V(G),÷v|L(v)|≥k,GÑ•3˜‡L-/Ú,@o·‚¡G´k-
LŒ/.GLÚê,^χ
l
(G) L«,´¦ãG´L-Œ/•êk.w,,éu?¿
ãG§χ
l
(G) ≥χ(G).
DP-/Ú´L/Ú?˜Úí2,32015c,•y²Ø¹4-8²¡ã´3-ŒÀ,
Dvoˇr´akÚPostle [3]Ú\éA/ÚVg(=:DP-/Ú).32018c, Bernshteyn ÚKostochka[4]
JÑDP-/Ú.
G´äkn‡º:{üã,L´V(G) ˜‡L˜.éuz^>uv∈E(G),-L(u)
ÚL(v)ƒm˜‡š•M
uv
(ؘ½´{š,•ŒU´˜).M
L
= {M
uv
: uv∈E(G)},
H
L
´÷ve¡o‡^‡ã:
DOI:10.12677/aam.2022.1175014761A^êÆ?Ð
¶——
•éuz˜‡:u∈V(G),L(u) /¤˜‡ã;
•éuz˜‡:u∈V(G) 'éH
L
¥˜‡:8L(u);
•euv/∈E(G),@oL(u) ÚL(v) ƒmع>;
•euv∈E(G),@oL(u)ÚL(v) ƒm>3M
uv
¥.
XJH
L
´˜‡•¹kn‡ƒÕá8,@oãGk˜‡M
L
-/Ú.eéuu∈V(G),
[k]⊆L(u)?¿šM
L
,§Ñk˜‡M
L
-/Ú,K¡ãG´DP-Œ/.GDP-Úê,^
χ
DP
(G) 5L«,´¦ãG´DP-Œ/•êk.L/Ú´DP-/Ú˜«AÏœ¹,
eéu?¿:u∈V(G),L˜L
0
÷v|L
0
(u)|=k.·‚Œ±3L
0
(u) Ú[k] ƒmïᘇV
.éuz^>uv∈E(G),-:uÚ:vƒm†L
0
(u) ÚL
0
(v)¥ƒ˜˜éAôÚ/
¤˜‡š•M
uv
.·‚Œ±•,ù‡M
L
-/Údu˜‡L
0
-/Ú.Ïd,éu?¿ãG,
χ
DP
(G) ≥χ
l
(G).
3ùŸ©Ù¥,·‚ïÄã/Ú8Ž{.Ä8Ž{´zg••ÄG˜‡º:,
·‚•Ä:už,lL(u)¥‰§©˜‡?¿ôÚ,'Xα.dž,•(/Ú´~,·
‚7LluØŒ^ôÚL¥£Øα.Ïd,uz‡ØLŒŒU¬~1,Ù§
¤kL±ØC.XJ3‡L§¥vk˜‡:LŒ~0(=z‡ ™/Úº:o´
–k˜«Œ^ôÚ),@o·‚ÒG˜‡~/Ú.ù‡Ž{ÚÑòzÝVg.
½Â1.1G´˜‡ã,f: V(G) →N•˜‡¼ê, éu:u∈V(G),/íØ0öŠ(G,f,u)
ãG
0
:= G−u,¼êf
0
: V(G
0
) →Zde¡ªf‰Ñ
f
0
(v) :=



f(v)−1,XJuv∈E(G);
f(v),Ù§œ¹.
XJ•ª¼êf
0
´šK,=é?¿v∈V(G
0
),Ñkf
0
(v)≥0,@o·‚¡T/íØ0ö
Š´k.XJ·‚Œ±ÏL˜Xk/íØ0öŠKG¥¤k:,@o·‚¡ãG
´f-òz.
ãDP-/ÚÚL/Ú˜‡«O´:3L/Ú¥,XJn´óê,@oχ
l
(C
n
) = 2,XJn
´Ûê,@oχ
DP
(C
n
) =3.3DP-/Ú¥,éu¤kn≥3,Ñkχ
DP
(C
n
) =3.Ïd,·‚•
Ä´ÄŒ±?U8/ÚL§5/•0˜ôÚ,χ
DP
(G) ˜‡•Ð.•.ù´ék
,Ïd,·‚ïĘ«{ü%érŒ•{.
•Ä:u∈V(G),w´§Ø.˜„5`,XJ·‚‰u/˜«ôÚc,@owŒU¬”
ôÚc.´,b|L(u)|>|L(w)|,=î‚5`uŒ^ôÚ'wõ.3ù«œ¹e,L(u)¥˜
½k˜«ôÚØÑy3L(w) ¥,¿…ù«ôÚ©‰u¿Ø¬K•L(w)(,,uÙ§ØŒU
E,¬”˜«ôÚ).ÏLù«•ª,·‚•w/•0˜«ôÚ.BernshteynÚLee[5]
JÑ±e½Â:
½Â1.2G´˜‡ã,f:V(G)→N•˜‡¼ê,éu˜éƒ:u,w∈V(G),/í
DOI:10.12677/aam.2022.1175014762A^êÆ?Ð
¶——
Ø•0öŠ(G,f,u,w) ãG
0
:= G−u,¼êf
0
: V(G
0
) →Zde¡ªf‰Ñ
f
0
(v) :=



f(v)−1,XJuv∈E(G),v6= w;
f(v),Ù§œ¹.
XJf(u)>f(w)…•ª¼êf
0
´šK,@o·‚¡T/íØ•0öŠ´k.
XJ·‚Œ±ÏL˜X k/íØ0Ú/íØ•0öŠKG¥¤k:,@o·‚¡ãG
´f-fòz.‰½d∈N,XJf= d,@o·‚¡G´d-fòz.GfòzÝ,PŠwd(G),
´¦G´d-fòz•dŠ.
‰½˜‡8ÜS⊆V(G),XJl(G,f)m©,¦S¥:=ÏLk/íØ0öŠK§
Ù§:Œ±ÏL˜Xk/íØ0Ú/íØ•0öŠK,@o·‚¡G´/S-f-fò
z0.AO/,G´/S-f-fòz0…=G´f-òz.
BernshteynÚLee[5]y²±e·Kµ
·K1.3[5]é?¿ãG,Ñ÷v
χ(G) ≤χ
l
(G) ≤χ
DP
(G) ≤χ
DPP
(G) ≤wd(G)+1≤∆(G)+1.
ùpχ
DP
(G)L«GDP-Úê,χ
DPP
(G)L«GDP-3‚Úê.
3[5]¥,Šöy²Brooks½nfòz‡:XJG´˜‡•ŒÝ∆≥3 ëÏã,@o
G´(∆−1)-fòz½öG
∼
=
K
∆+1
.·‚•,GDPä´˜‡ëÏã,z‡¬´˜‡ ã½
ö˜‡.3[5]¥Šöy²-G´˜‡ëÏã,@oe¡ ü^´d:(1) G´(d−1)-fò
z;(2) GØ´˜‡GDPä.Šö„y²-G´˜‡š˜ã,XJGfòzÝ–•d≥3,
@oG•¹˜‡(d+1)-ì½ö
mad(G) ≥d+
d−2
d
2
+2d−2
.
¯¢y²,¦^/íØ0Ú/íØ•0öŠ•{Œ±y²A‡š²…þ..1994c,
Thomassen[6]y²¤k²¡ã´5-ŒÀ;2015c,Dvoˇr´akÚPostle[3]y²¤k²¡ã
´DP-5-Œ/;2021 c,Bernshteyn ÚLee[5]JÑfòzÝVg,2grù˜(J?1\r,
¦‚y²¤k²¡ã´4-fòz.
ˇ
Skrekovski[7]y²عK
5
-fªã´5-ŒÀ;5§Shen[8]<‰Ñ,˜«•{y
²Ø¹K
5
-fªã´5-ŒÀ;Wang[9]<y²عK
5
-fªã´DP-5-Œ/.·‚\
rT(J§y²Xe½n:
½n1.4¤kعK
5
-fªã´4-fòz.
Lam[10]<y²ع4-²¡ã´4-ŒÀ;KimÚOzeki[11]y²ع4-²¡
ã´DP-4-Œ/.e¡òT(Jí2ùaã•´3-fòz.
½n1.5ع4-²¡ã´3-fòz.
DOI:10.12677/aam.2022.1175014763A^êÆ?Ð
¶——
Wang[12]<y²ع4-†3-ƒ²¡ã´4-ŒÀ;KimÚYu[13]y²ع
4-†3-ƒ²¡ã´DP-4-Œ/.·‚U?ù‡(J§y²e¡½n:
½n1.6ع4-†3-ƒ²¡ã´3-fòz.
òGi\˜‡²¡¥,·‚˜‡²¡ãG=(V,E,F),Ù¥V,E,F©OL«Gº
:!>Ú¡8Ü.éu˜‡8ÜS⊆V(G),G[S] L«dSpGfã.éu :v∈V,v3
G¥ÝêL«•d
G
(v),Ý•d(–•d½–õ•d):¡•d-:(d
+
-:½d
−
-:).ÎÒd-¡,
d
+
-¡,d
−
-¡•aq½Â.éu¡f∈F,XJf>.þ:Uì^ž^Sv
1
,v
2
,...,v
k
ü§@
o·‚PŠf= [v
1
v
2
...v
k
v
1
],¿…¡f•˜‡( d
G
(v
1
),d
G
(v
2
),...,d
G
(v
k
) )-¡.ãG•ÝÚ•
ŒÝ©O•δ(G)=min{d
G
(v)|v∈V(G)}Ú∆(G)=max{d
G
(v)|v∈V(G)}.XJü‡¡()–
k˜^ú>,@o§‚´ƒ.XJü‡¡()ƒ…TÐk˜^ú>,K·‚¡§‚´
~ƒ.éu²¡ãG¥C,XJCSÜÚÜѹkG¥:,@o·‚¡C•G
˜‡©l. ˜^>,·‚•´lã¥íKù^>,Óžrù^>à:Ê3˜å.XJ
ÏL G,>Ú(½ö)íØ:Ú>ã¥,Œ±/¤˜‡ÓuHã,@o·‚¡H
•G˜‡fª.XJHØ´G˜‡fª,@oG¡•Ø¹H-fª.xÚy•G¥ü‡ØÓ
:.XJ3G¥xÚy´Øƒ,·‚^G+xyL«3G¥rxyëå5ã.G−vL«
3G¥íK:vÚ¤k†Ù'é>ã.
2.عK
5
-fªã
²¡n¿©´˜«i\ª²¡ã,§z‡¡Ñ±˜‡•Ý•3•.,Cqn¿©ã
•´˜«i\ª²¡ã,Ù¥z‡k.¡±˜‡n/•.,Ã.¡(Ü¡)±˜‡•..ü‡
ãG
1
ÚG
2
`-Ú´•G= G
1
S
G
2
…G= G
1
T
G
2
= K
`
.
Wagnerã[14](„ã1)˜‡k8‡º:,12^>3Kã.5¿Tã´š²¡ã,Ïd,§
ØU´²¡ãfã.عK
5
-fª4Œ>ãG•§عK
5
-fª,´éuG¥?¿ü
‡Øƒº:xÚy,G+xy•¹˜‡K
5
-fª.
Figure1.Wagnergraph
ã1.Wagnerã
DOI:10.12677/aam.2022.1175014764A^êÆ?Ð
¶——
½n2.1£Wagner[14]¤z‡Ø¹K
5
-fª4Œ>ãÑŒ±ÏLWagnerãÚ²¡n
¿©ã2-Ú†3-ÚØäÊë¤.
½n2.2[5]G´˜‡–k3 ‡:²¡ã,Ù¥z‡šÜ¡Ñ´n/,…Ü
¡´˜‡k•C, C>.þ:Uì^ž^Sv
1
,v
2
,...,v
k
ü.½Âf: V(G)\{v
1
,v
2
}→Z
•
f(u) :=



2−|N
G
(u)∩{v
1
,v
2
}|,XJu∈V(C);
4−|N
G
(u)∩{v
1
,v
2
}|,Ù§œ¹.
@oG−v
1
−v
2
´/(V(G)\{v
1
,v
2
})-f-fòz0.
Ún2.3G´˜‡Cqn¿©ã,f•G˜‡~¼ê,¿…é?¿v∈V(G) þ÷
vf(u)=4 −|N
G
(u)∩{v
1
,v
2
}|.bH•G˜‡ÓuK
3
fã,λ´H¥¤k:˜‡S
§¦3ù‡SeŒ±²L˜Xk/íØ0Ú/íØ•0öŠKH¥¤k:.@
o·‚Œ±3ù‡SÄ:þ?U¤˜‡#S,¦3dSeŒ±ÏL˜Xk/í
Ø0Ú/íØ•0öŠKG¥¤k:.=G´4-fòz.
y²æ^‡y{,bù‡Ún´†Ø,-G´˜‡:ê•4‡~.·‚b
H'K
3
ÚV(H) = (u,v,w).
œ¹1µHØ´G˜‡©l3-.duG´˜‡Cqn¿©ã,·‚Œ±-#xÑTã,
¦H´GÜ¡.5¿G
0
=G−w•´Cqn¿©ã,k‰Hþ:wüS,XJx
Úw´ƒ,-f
0
(x) = 3−|N
G
(x)∩{u,v}|.Ù¦œ¹e,Ñkf
0
= f.Šâ½n2.2,Œ±3u,v
SÄ:þ?U¤ãG˜‡S,¦3ù‡SeŒ±ÏL˜Xk/íØ0Ú/íØ
•0öŠKG¥¤k:,l¤Úny².
œ¹2µH´G˜‡©l3-.-G
1
L«¤k:Ú>3HSܽHþ˜‡ã,G
2
L
«¤k:Ú>3HܽHþ˜‡ã.aquþãy²,·‚Œ±3HSλÄ:þ?U
¤G
1
˜‡S,Ó?U¤G
2
˜‡S.(Üüö,·‚G˜‡S§¦3ù‡
Se,Œ±ÏL˜Xk/íØ0Ú/íØ•0 öŠKG¥¤k:.ÏdG´f-fò
z,Ún2.3y..
Ún2.4G´˜‡¹k4Œ>عK
5
-fªã,…é?¿u∈V(G),f(u)=4−
|N
G
(u)∩{v
1
,v
2
}|.bH´G˜‡ÓuK
2
½öK
3
fã, λ´H¥¤k:˜‡S§¦
3ù‡SeŒ±²L˜Xk/íØ0Ú/íØ•0öŠKH¥¤k:.@o·‚
Œ±3ù‡SÄ:þ?U¤ãG˜‡S,¦ÏL˜Xk/íØ0Ú/íØ•0ö
ŠKG¥¤k:.=dH´f-fòzŒ±ãG´f-fòz.
y²·‚é|V(G)|Š8B 5y²TÚn,XJG´Cqn¿©ã,@o ù‡(JŒ±†
lÚn2.3.XJH=y
1
y
2
,·‚Œ±by
1
y
2
u˜‡3-¡[y
1
y
2
y
3
],@ow,3HS
Ä:þŒ±?U¤G
0
= [y
1
y
2
y
3
]˜‡S.lT¯KŒ±{z•Ún2.3œ¹.
XJG´Wagnerã,@ow,G´f-fòz.
bGQ Ø´˜‡²¡n¿©•Ø´Wagner ã,3ù«œ¹e,dWagner ½n[14]Œ±
ÑG= G
1
S
G
2
,Ù¥G
1
,G
2
´Gfã,÷vG
1
T
G
2
'K
2
½öK
3
.w,,H⊆G
1
½G
2
.Ø”
DOI:10.12677/aam.2022.1175014765A^êÆ?Ð
¶——
H⊆G
1
,3G
1
þA^8Bb,3HSÄ:þŒ±?U¤G
1
˜‡S,ù)G
1
T
G
2
˜‡S.3G
2
þA^8Bb ,Œ±òH3G
1
T
G
2
SÄ:þ?U ¤G
2
˜‡S.ù
Ò)G˜‡S,…3ù‡Se,Œ±ÏL˜Xk/íØ0Ú/íØ•0öŠ
KG¥¤k:,ÏdG´f-fòz.Ún2.4y..
½n1.4¤kعK
5
-fªã´4-fòz.
y²duz‡Ø¹K
5
-fªã´˜‡¹k4Œ>عK
5
-fªã)¤fã,Ïd,·‚
•I‡y²¹k4Œ>عK
5
-fªã)¤fã´4-fòz=Œ.·‚Œ±Äk‰G¥ü‡
ƒº:üS,ŠâÚn2.4Œ•§·‚Œ ±3dÄ:þ?U ¤ãG˜‡S§¦3ù‡ S
eŒ±²L˜Xk/íØ0Ú/íØ•0öŠKG¥¤k:.½n1.4y..
3.ع4-²¡ã
½n4.1éuk∈{3,5,6},XJG´Ø¹k-ã,@oG´3-òz.
y²Gع3-ž,GŒ•–•4.·‚Œ±†lî.úªy²Ø¹3-²¡ã
´3-òz.LihÚWang[15]y²ع5-²¡ã´3-òz.MoharÚJuvan[16]<y²
ع6-²¡ã´3-òz.½n4.1y..
éuع4-²¡ã,•3ùãGØ´3-òz(~X•Ä›¡Nã‚ã),·‚ò
y²Ø¹4-²¡ã´3-fòz.Ø”ع4-²¡ã•G,3[10] ¥,ŠöF
3
5
´d˜
‡5-Ú˜‡ƒ3-|¤ã.=V(F
3
5
) ={v
1
,v
2
,v
3
,v
4
,v
5
,v
6
},Ù¥v
1
,v
2
,v
3
,v
4
,v
5
,v
6
/¤
˜‡6-,v
2
v
6
•˜^u,-H´G˜‡fã,XJH†F
3
5
Ó,¿…éu?¿:vÑ÷v
d
G
(v) = 4,@oH¡•F
3
5
fã.
Ún4.2[10]G´˜‡Ø¹4-…عƒ3-²¡ã,XJδ(G)=4,@oG•¹˜
‡F
3
5
-fã.
½n1.5ع4-²¡ã´3-fòz.
y²G´˜‡4‡~,=éu˜‡Ø¹4-²¡ãG, GØ´3-fòz,´éuG
?¿fãÑ´3-fòz.ŠâÚn4.2,·‚•G•¹˜‡F
3
5
-fãH.-G
0
:= G−V(H),
f≤3´V(G)˜‡~¼ê.ŠâG45,·‚Œ±ÏL˜Xk/íØ0Ú/í
Ø•0öŠK(G
0
,f)¥¤k:.y3·‚•ÄãH,Äk/íØv
6
•v
5
0,,U
ìv
1
,v
2
,v
3
,v
4
,v
5
^S/íØ/•e:.3dL§¥ù‡/íØ•0Ú/íØ0öŠ´k
,ÏdH•´3-fòz.ù†·‚ÀJGgñ,½n1.5y.
4.ع4-†3-ƒ²¡ã
½n1.6ع4-†3-ƒ²¡ã´3-fòz.
y²b½nؤá,-G´˜‡:ê•4‡~,Šâ·‚b,Gke¡5Ÿ:
•(a) G´ëÏã;
DOI:10.12677/aam.2022.1175014766A^êÆ?Ð
¶——
•(b) G¥vkÓu4-†3-ƒfã;
•(c) GØ´3-fòz;
•(d) Gz‡fãG
0
´3-fòz.
Ún4.1G¥vk3
−
-:.
y²bG¥•3˜‡3
−
-:v,@o·‚òy²G´3-fòz.-f´V(G) þ~¼
ê.ŠâG45,·‚ Œ±ÏL˜Xk/íØ0Ú/íØ•0öŠK(G−v,f) ¥
¤k:.duv´˜‡3
−
-:,·‚•I‡•/íØ0:v=Œ.Ún4.1y..
e5,·‚½ÂA‡ØÓ5-¡.f´G˜‡5-¡.
•(a) XJf´˜‡(4,4,4,4,4)-¡,@o·‚¡f•5-¡.XJf†˜‡3-¡f
0
=[vv
1
v
2
v] ƒ
,Ùú>•v
1
v
2
,@o·‚¡v´f˜‡.Ó,¡f¡•v˜‡®.(„ã2¥F
1
).
•(b)XJf´˜‡(5
+
,4,4,4,4)-¡,¿…f†o‡3-¡Ú˜‡4
+
-¡ƒ,¿…4
+
-¡†fþ
5
+
-:'é,@o·‚¡f•˜‡€5-¡.(„ã2¥F
2
).
•(c) XJf´˜‡(5
+
,4,4,4,4)-¡,¿…f†Ê‡3-¡ƒ,@o·‚¡f•˜‡AÏ5-¡.Ó
ž,·‚¡fþ5
+
-:•˜‡AϺ:.(„ã2¥F
3
).
Figure2.Definitionofdifferent5-faces
ã2.ØÓ5-¡½Â
I54.2
•(1)˜‡AϺ:–'阇AÏ5-¡,˜‡AÏ5-¡TІ˜‡AϺ:'é;
•(2)XJ3˜‡5-¡fþ•3ü‡5
+
-:,@ofQØ´˜‡AÏ¡•Ø´˜‡€¡.
Ún4.3z‡Ñ´˜‡5
+
-:.
y²f=[v
1
v
2
v
3
v
4
v
5
v
1
]´˜‡5-¡,z´f˜‡.dÚn4.1Œ•G¥Ø•3
3
−
-:,Ïd·‚Œ±bd
G
(z)=4.Ø”˜„5,·‚Œ±bz†v
1
Úv
2
ƒ.G[S]•
S={z,v
1
,v
2
,v
3
,v
4
,v
5
}pGfã.•ÄGfãG
0
:=G−V(G[S]).Šâ(d),G
0
´3-f
òz.,·‚•ÄG[S],Äk/íØv
1
•z0,,Uìv
5
,v
4
,v
3
,v
2
,z^S/ íØ0•{
DOI:10.12677/aam.2022.1175014767A^êÆ?Ð
¶——
:.dL§¥/íØ•0Ú/íØ0öŠ´k,¤±G[S]´3-fòz.G•´3-fò
z.ù†(c)´gñ,Ïdd
G
(z) ≥5.Ún4.3y..
äó4.4v´G˜‡5
+
-:,Ke¡(ؤá:
•(1)v•õ'é
j
d(v )
2
k
‡3-¡;¿…
•(2)XJv†t‡3-¡'é…2t<d
G
(v)§@ov•õ'ét−1 ‡AÏ5-¡.
y²5¿(1)w,l(b)¥Œ±.
ŠâAÏ5-¡½Â,XJv´G˜‡5
+
-:,@ oz‡†v'éAÏ5-¡Ñ†ü‡3-¡
ƒ,¿…ùü‡3-¡Ñ†v'é,Ïd(2)¤á.äó4.4y..
Ún4.5v´G˜‡5
+
-:,bv†˜‡AÏ5-¡½ö€5-¡f
1
Ú˜‡3-¡f
2
'é,
¿…f
1
Úf
2
ƒ,@ovvkuf
2
®.
y²f
1
= [vv
4
v
3
v
2
v
1
v] ´˜‡AÏ5-¡½ö€5-¡.ŠâAÏ5-¡½ö€5-¡½Â,–
ko‡3-¡†f
1
ƒ.bf
2
= [vv
5
v
4
v],…f
2
†f
1
ƒ(„ã3).|^‡y{,bvk˜‡
®f
3
= [v
4
v
5
v
6
v
7
v
8
v
4
]†f
2
ƒ,Ù¥v
4
v
5
•§‚ú>,@ov
3
´f
3
˜‡.,,v
3
´˜
‡4-:,ù†Ún4.3gñ.Ún4.5y..
Figure3.IllustrationofLemma4.5
ã3.Ún4.5«¿ã
Ú n 4.6f
1
Úf
2
´ü‡€5-¡,@o§‚ØU†˜^ú>vv
1
~ƒ,Ù¥v´f
1
Úf
2
þ5
+
-:.
y²bf
1
Úf
2
´ü‡€5-¡,§‚´~ƒ,§‚k˜‡ú5
+
-:vÚ˜^ú
>vv
1
(„ã4).Ï•f
1
Úf
2
Ñ´€5-¡,@ov
1
´˜‡4-:,f
3
=[v
1
v
3
v
4
v
1
] Úf
4
=[v
1
v
2
v
3
v
1
]
´ü‡3-¡.Ïd,f
3
Úf
4
´ƒ,ù†(b)gñ,Ïdb´†Ø.Ún4.6y..
= £Äk,·‚½Â˜‡Xã5¤«˜‡..3ã5¥,xÚº:Ýê–´'é>
êþ,çÚº:Ýêu'é>êþ.ùÚº:v´˜‡AÏ5-:,§†˜‡AÏ5-¡f
1
,
˜‡€5-¡f
2
Ú˜‡5-¡f
3
'é,…÷v±e^‡:
•f
3
QØ´AÏ5-¡•Ø´€5-¡;¿…
•f
3
†˜‡AÏ5-:v'é,…v†˜‡€5-¡f
2
'é;¿…
•f
3
†f
2
~ƒ.
DOI:10.12677/aam.2022.1175014768A^êÆ?Ð
¶——
Figure4.IllustrationofLemma4.6
ã4.Ún4.6«¿ã
Figure5.Special5-vertexand
incident5-faces
ã5.AÏ5-:†'é5-¡
·‚¡F
5
•f
3
8Ü,=F
5
´d¤k5-¡|¤8Ü,§‚†f
3
kƒÓ5Ÿ.·‚¡ù
˜‡AÏ5-:v•«¡AÏ5-:.
I54.7w•f
3
˜‡º:,Xã5¤«.XJd
G
(w)= 4,@oŠâ(b),w•õ'阇
3-¡.
dî.úª|V|−|E|+|F|= 2Úúª
P
v ∈V
d
G
(v) = 2|E|=
P
f∈F
d
G
(f).·‚Œ±Ñ
X
v ∈V
(2d
G
(v)−6)+
X
f∈F
(d
G
(f)−6) = −12.
y3·‚éz‡x∈V
S
F½Â˜‡Ð©-ch(x),éz‡v∈V,ch(v)=2d
G
(v) −6,
z‡f∈F,ch(f)=2d
G
(f) −6.·‚òO·=£5K.du=£L§¥,oŠ
´½,XJ·‚òЩŠch(x) UC••ªŠch
0
(x),¦éuz‡x∈V
S
F,Ñ÷v
ch
0
(x) ≥0,@o
0 ≤
X
x∈V∪F
ch(x) =
X
x∈V∪F
ch
0
(x) = −12.
ùò´˜‡gñ.ù¿›X½n¥‡~Ø•3,Ïd½n¤á.
DOI:10.12677/aam.2022.1175014769A^êÆ?Ð
¶——
·‚^c(v→f)L«lv=£‰fŠ,Ù¥v∈V(G)Úf∈F(G).
=£L§Xe:
•(R1)XJv´˜‡4
+
-:…f´§'é3-¡,@oc(v→f) = 1;
•(R2)XJv´˜‡4
+
-:…f´§'é4-¡,@oc(v→f) =
1
2
;
•(R3)XJv´˜‡–õ†˜‡3-¡'é4-:,f´˜‡†v'é5-¡, @oc(v→f) =
(
1
4
,XJvTІ˜‡3-¡Ú˜‡4-¡'é;
1
3
,Ù¦œ¹.
•(R4)ŠâIP4.2(1),˜‡AÏ5-¡TІ˜‡AϺ:'é.v´˜‡ AÏ5
+
-:,f´˜
‡†v'é5-¡,@oc(v→f) =







1,XJf´AÏ5-¡;
2
3
,XJd
G
(v) = 5 …f´€5-¡(„ã5¥f
2
);
1
3
,XJd
G
(v) = 5,v´«¡,…f∈F
5
(„ã5¥f
3
).
•(R5)XJvØ´˜‡AÏ5-:½6
+
-:,…f´˜‡†v'é€5-¡,@oc(v→f) =
3
4
;
•(R6)XJv´f˜‡,@oc(v→f) =
1
5
;
•(R7)XJv´6
+
-:½Ø´˜‡AÏ5-:,½ö´˜‡Ø†˜‡€5-¡'éAÏ5-:,…X
JfØ´˜‡AÏ5-¡½ö€5-¡,Ù¥f†v'é,@oc(v→f) =
1
2
.
‡¤½n1.6y²,„I‡uV
S
F¥z‡ƒ•ªŠ´Ä´šK,e¡ü^ä
óòéd?1`².
äó4.8éu¤kv∈V(G),ch
0
(v) ≥0.
y²ŠâÚn4.1,G¥Ø•33
−
-:,Ïd·‚I‡3e¡•Ä4
+
-:.
œ¹1µd
G
(v) = 4.
3ù«œ¹e,·‚kch(v) =4×2−6 = 2.ŠâÚn4.3,vvk?Û®.XJv†ü‡3-¡
'é,@oŠâR1,ch
0
(v) = ch(v)−2×1 = 0.
XJvTІ˜‡3-¡ 'é,@oŠ â(b)Œ•,v•õ†˜‡4-¡'é.bv†˜‡4-¡'
é,@o§•õ†ü‡5-¡'é.ŠâR1,R2ÚR3,ch
0
(v) ≥ch(v)−1−
1
2
−
1
4
×2 = 0.ÄK,v•
õ'én‡5-¡.ŠâR1ÚR3,ch
0
(v) ≥ch(v)−1−
1
4
×3 >0.
XJv؆?Û3-¡'é,@oŠâR2ÚR3,ch
0
(v) ≥ch(v)−
1
2
×4 = 0.
œ¹2µd
G
(v) = 5.
3ù«œ¹e,·‚kch(v)=5×2−6=4.ŠâI54.2(1),bv´AÏ:,=v†˜‡
AÏ5-¡'é.dÚn4.4ÚAÏ5-¡½ÂŒ•,vTІü‡3-¡ Ú˜‡AÏ5-¡'é.ŠâÚ
n4.5,vvk®.XJv†˜‡€5-¡'é,ŠâÚn4.6Œ•, v•õ†˜‡€5-¡'é.Ïd·‚
DOI:10.12677/aam.2022.1175014770A^êÆ?Ð
¶——
Œ±lR1ÚR4¥ch
0
(v) ≥ch(v)−1×2−1−
2
3
−
1
3
= 0.ÄKv؆?Û€5-¡'é,Šâ
R1,R4ÚR7,ch
0
(v) ≥ch(v)−1×2−1−
1
2
×2 = 0.
e5·‚bvØ´AÏ:,=dI54.2 (1) Œ•,v؆?ÛAÏ5-¡'é.ŠâÚn4.4
(1),v•õ†ü‡3-¡'é.ŠâÚn4.6,v•õ†ü‡€5-¡'é.
•XJvuü‡3-¡,@oŠâÚn4.6,€5-¡½ÂÚ(b)Œ•,v–õ†˜‡€
5-¡'é.Šâ(b),v؆?Û4-¡'é.Ïd,ŠâR1,R4,R6ÚR7,·‚Œ±Ñ
ch
0
(v) >ch(v)−1×2−1−
3
4
−
1
2
×2 >0.
•XJvTІ˜‡3-¡'é,@oŠ â€5-¡½Â,v•õ†ü‡€5-¡'é,ÏdŠ âR1,
R4,R6ÚR7,ch
0
(v) >ch(v)−1−
1
5
−
3
4
×2−
1
2
×2 >0.
•XJv؆?Û3-¡'é§@ov؆?Û€5-¡'é.ŠâR2 ÚR7,ch
0
(v) ≥ch(v)−
1
2
×5 >
0.
œ¹3µd
G
(v) = 6.
5¿ch(v) = 2×6−6 = 6.ŠâÚn4.4,v•õ'én‡3-¡,•õ'én‡AÏ5-¡.
•bv†n‡3-¡'é.XJv†n‡AÏ5-¡'é,@oŠâÚn4.5Œ•,vvk?Û®.
ŠâR1ÚR4,ch
0
(v) ≥ch(v)−3−3 = 0.ÄKv•õ'éü‡AÏ5-¡.ŠâÚn4.5Œ•,
vvk?Û®.ŠâR1,R4ÚR5,ch
0
(v) ≥ch(v)−3−2−
3
4
>0.
•bv•õ†ü‡3-¡'é,@oŠâÚn4.4(2)Œ•,v•õ†˜‡AÏ5-¡'é.XJv†
˜‡AÏ5-¡'é,@oŠâR1,R4,R5ÚR6Œ,ch
0
(v) >ch(v)−2(1+
1
5
)−1−
3
4
×3 >0.
ÄKŠâÚn4.6,v•õ†ü‡€5-¡'é.Ïd,ŠâR1,R4,R5,R6ÚR7,·‚Œ±Ñ
ch
0
(v) >ch(v)−2(1+
1
5
)−
3
4
×2−
1
2
×2 >0.
œ¹4µd
G
(v) = 7.
3ù«œ¹e§ch(v)=2×7−6 =8.ŠâÚn4.4,v•õ'én‡3-¡,•õ'éü‡AÏ
5-¡.ŠâR1,R4,R5ÚR6,•ªŠ••ch
0
(v) >ch(v)−3(1+
1
5
)−2−
3
4
×2 >0.
œ¹5µd
G
(v) = k≥8.
5¿ch(v)=2k−6.ŠâÚn4.4,v•õ'é
j
d(v )
2
k
‡3-¡,•õ'é
j
d(v )
2
k
‡AÏ5-¡.
ŠâR1,R4ÚR6,Œ±Ñch
0
(v) ≥ch(v)−(1+
1
5
)×
j
d(v )
2
k
−1×
j
d(v )
2
k
>0.
äó4.8y..
äó4.9éu¤kf∈F(G),ch
0
(f) ≥0.
y²f´G˜‡¡,Ï•G´{üã,¤±Gvk‚Úõ->.d
G
(f)≥3.XJ
d
G
(f) ≥6, @ofQØlO?Š, •Ø•=ÑŠ. Ïd§ch
0
(f) = ch(f) = d
G
(f)−6 ≥0.
XJd
G
(f)=3,@oŠâR1,†f'éz‡:=1‰f.Ïd,·‚Œ±ch
0
(f)=
ch(f) +3×1=d
G
(f) −6+3=0.XJd
G
(f)=4,@oŠâR2,†f'éz‡:=
1
2
‰
f,Ïd•ªŠch
0
(f)=ch(f)+ 4×
1
2
=d
G
(f) −6 +2=0.e5·‚bd
G
(f)=5,@o
ch(f) = 5−6 = −1.
DOI:10.12677/aam.2022.1175014771A^êÆ?Ð
¶——
œ¹1µf´5-¡,=†f'é¤k:Ñ´4-:.
éu0≤t≤5,t•fþ†ü‡3-¡'é4-:ê8,@ofþk(5−t) ‡4-:–õ'
阇3-¡,¿…f–k(t+1) ‡.Ïd,ŠâR3ÚR6,éuz‡t∈{0,1,2,3,4,5}§Ñk
ch
0
(f) ≥−1+
1
4
×(5−t)+
1
5
×(t+1) =
9−t
20
>0.
œ¹2µf´˜‡(5
+
,4,4,4,4)-¡.
^vL«5
+
-:,XJf´˜‡AÏ5-¡,@oŠâR4,ch
0
(f) ≥−1+1 = 0.e5·‚b
fØ´˜‡AÏ5-¡,@oŠâAÏ5-¡½ÂŒ•,•3˜‡4-:•õ†f˜‡3-¡'é.
•bv´˜‡AÏ5-:,…v†˜‡€5-¡'é.XJf´€,@ok˜‡4-:(ã5
¥†vƒ4-:)TІ˜‡3-¡'é,؆fþ?Û4-¡'é.ŠâR3ÚR4,
ch
0
(f)≥−1 +
2
3
+
1
3
=0.ÄKfØ´€5-¡,@of∈F
5
,v´˜‡«¡AÏ5-:.5¿
ã5¥fÒ´f
3
.Ïd,ŠâI54.7,f–†ü‡4-:'é,…ùü‡4-:•õ'阇
3-¡,…ØÓž'阇3-¡Ú˜‡4-¡.ŠâR3,R4ÚR7,ch
0
(f) ≥1+
1
3
+
1
3
+
1
3
= 0.
•ÄK,v´˜‡6
+
-:,½övØ´˜‡AÏ5-:,½öv´˜‡AÏ5-:…v؆˜‡€5-¡
'é.XJf´€5-¡,@o•3˜‡†f'é4-:,¿…ù‡4-:•õ'阇3-¡.Š
âR3ÚR5,ch
0
(v)≥−1+
1
4
+
3
4
=0.XJfØ´€5-¡,@of–'éü‡4
+
-:,¿…
ùü‡4
+
-:•õ'阇3-¡.ŠâR3ÚR7,ch
0
(f) ≥−1+
1
4
×2+
1
2
= 0.
œ¹3µfþ–•3ü‡5
+
-:.
lI54.2(2)Œ•,fQØ´AÏ5-¡•Ø´€5-¡.
•XJf∈F
5
,@oŠâI54.7,R3,R4ÚR7,ch
0
(f) ≥−1+
1
3
×2+
1
3
= 0.
•XJf/∈F
5
,=f؆˜‡AÏ5-:'é,Ù¥ù‡5-:3˜‡AÏ5-¡þ…†˜‡€5-¡
'é.ŠâR7,ch
0
(f) ≥−1+
1
4
×2+
1
2
= 0.
½n1.6y..
ë•©z
[1]Vizing,V.G.(1976)VertexColorings withGivenColors.MetodyDiskretnogoAnalizaNovosi-
birsk,29,3-10.(InRussian)
[2]Erd˝os,P.,Rubin,A.L.andTaylor,H.(1979)ChoosabilityinGraphs.CongressusNumeran-
tium,26,125-127.
[3]Dvoˇr´ak, Z. andPostle, L. (2018)Correspondence Coloring andItsApplicationtoList-Coloring
PlanarGraphswithoutCyclesofLengths4to8.JournalofCombinatorialTheory,SeriesB,
129,38-54.https://doi.org/10.1016/j.jctb.2017.09.001
DOI:10.12677/aam.2022.1175014772A^êÆ?Ð
¶——
[4]Bernshteyn,A.andKostochka,A.(2018)OnDifferencesbetweenDP-ColoringandListCol-
oring.SiberianAdvancesinMathematics,21,61-71.
[5]Bernshteyn,A.andLee,E.(2021)WeakDegeneracyofGraphs.arXiv:2111.05908
[6]Thomassen,C.(1994)Every PlanarGraphIs5-Choosable.JournalofCombinatorialTheory,
SeriesB,62,190-191.https://doi.org/10.1006/jctb.1994.1062
[7]
ˇ
Skrekovskiv,R.(1998)ChoosabilityofK
5
-Minor-FreeGraphs.DiscreteMathematics,190,
223-226.https://doi.org/10.1016/S0012-365X(98)00158-7
[8]He,W.,Miao,W.andShen,Y.(2008)AnotherProofofthe5-ChoosabilityofK
5
-Minor-Free
Graphs.DiscreteMathematics,308,4024-4026.
[9]Li,L.andWang,T.(2022)AnExtensionofThomassen’sResultonChoosability.Applied
MathematicsandComputation,425,ArticleID:127100.
https://doi.org/10.1016/j.amc.2022.127100
[10]Lam,P.C.B., Xu,B. andLiu,J. (1999) The4-Choosability ofPlaneGraphswithout4-Cycles.
JournalofCombinatorialTheory,SeriesB,76,117-126.
https://doi.org/10.1006/jctb.1998.1893
[11]Kim,S.J.andOzeki,K.(2018)ASufficientConditionforDP-4-Colorability.DiscreteMathe-
matics,341,1983-1986.https://doi.org/10.1016/j.disc.2018.03.027
[12]Cheng,P.,Chen,M.andWang,Y.(2016)PlanarGraphswithout4-CyclesAdjacenttoTri-
anglesAre4-Choosable.DiscreteMathematics,339,3052-3057.
https://doi.org/10.1016/j.disc.2016.06.009
[13]Kim,S.J.andYu,X.(2019)PlanarGraphswithout4-CyclesAdjacenttoTrianglesAreDP-
4-Colorable.GraphsandCombinatorics,35,707-718.
https://doi.org/10.1007/s00373-019-02028-z
[14]Wagner, K. (1937)
¨
Uber eine Eigenschaft der ebenen Komplexe. MathematischeAnnalen, 114,
570-590.https://doi.org/10.1007/BF01594196
[15]Wang, W.and Lih,K.W.(2002) Choosabilityand EdgeChoosabilityof PlanarGraphs without
FiveCycles.AppliedMathematicsLetters,15,561-565.
https://doi.org/10.1016/S0893-9659(02)80007-6
[16]Fijavˇz,G.,Juvan,M.,Mohar,B.and
ˇ
Skrekovski,R.(2002)PlanarGraphswithoutCyclesof
SpecificLengths.EuropeanJournalofCombinatorics,23,377-388.
https://doi.org/10.1006/eujc.2002.0570
DOI:10.12677/aam.2022.1175014773A^êÆ?Ð

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