平面图和不含 K5-子式图的弱退化度 Weak Degeneracy of Planar Graphs andK5-Minor-Free Graphs

设为首页加入收藏期刊导航网站地图

期刊菜单

文章导航

AdvancesinAppliedMathematics A^êÆ?Ð,2022,11(7),4760-4773

PublishedOnlineJuly2022inHans.//www.abtbus.com/journal/aam

https://doi.org/10.12677/aam.2022.117501

² ¡ãÚØ¹K

- 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)≤χ

( G) ≤

( G) ≤d+1 "3ùŸØ©¥§·‚y²Ø¹K

- fªã´4- fòz¶Ø¹4- ²¡

ã ´3-fò z¶Ø¹4-†3-ƒ²¡ã ´3-fò z"

' …c

ò zÝ§fò zÝ§²¡ã §•§=£

WeakDegeneracyofPlanarGraphsand

-Minor-FreeGraphs

XiaoxiaoDing

CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang

Received:Jun.19

,2021;accepted:Jul.14

,2022;published:Jul.21

,2022

Abstract

WeakdegeneracyofgraphsisanewdeﬁnitionproposedbyBernshteynandLee.It

- fªãfòzÝ[J]. A^êÆ?Ð,2022,11(7):4760-4773.

DOI:10.12677/aam.2022.117501

¶ ——

isthedeformationofthedegeneracyofgraphs.Bydeﬁnition,every d-degenerate

graphisalsoweakly d-degenerate.Ontheotherhand,if Gisweakly d-degenerate,

then χ(G)≤χ

( G) ≤χ

( G) ≤d+1 .Inthispaper,weprovethatplanargraphswith

-minor-freeareweakly4-degenerate,planargraphswithout4-cyclesareweakly

3-degenerateandplanargraphswithout4-cyclesadjacentto3-cyclesareweakly3-

degenerate.

Keywords

Degeneracy,WeakDegeneracy,PlanarGraphs,TheLengthofCycles,Discharging

 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 /Ú´~.

G k˜‡~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-Œ/ .X Jé? ¿•½

ô ÚLL,¦éz‡v∈V(G),÷v|L(v)|≥k,GÑ•3˜‡L-/Ú,@o·‚¡G´k-

L Œ/.GL Úê,^χ

( G) L«, ´¦ãG´L- Œ/•êk. w,, éu?¿

 ãG§χ

( G) ≥χ( G).

DP -/Ú´L/Ú?˜Úí2,32015c,•y²Ø¹4-8²¡ã´3-ŒÀ,

Dvoˇr´ak ÚPostle [3] Ú\éA/ÚVg( =: DP- /Ú). 32018 c, Bernshteyn ÚKostochka[4]

J ÑDP-/Ú.

 G´ äkn‡º:{üã,L´ V(G)˜‡L˜.éuz^>uv∈E(G),-L(u)

Ú L(v)ƒm˜‡š•M

( Ø˜½´{š, •ŒU´˜). M

= {M

: uv∈E( G) },

´ ÷ve¡o‡^‡ã:

DOI:10.12677/aam.2022.1175014761 A^êÆ?Ð

¶ ——

• éuz˜‡:u∈ V(G),L(u)/¤˜‡ã;

• éuz˜‡:u∈ V(G)'éH

¥ ˜‡:8L(u);

• euv/∈E(G),@oL(u)ÚL(v)ƒmØ¹>;

• euv∈ E(G),@oL(u)ÚL(v)ƒm>3M

¥ .

X JH

´ ˜‡•¹kn‡ƒÕá8,@oãGk˜‡M

- /Ú. eéuu∈V( G),

[ k] ⊆L( u) ?¿šM

, §Ñk˜‡M

- /Ú, K¡ãG´DP- Œ/. GDP- Úê, ^

( G) 5L«, ´¦ãG´DP- Œ/•êk. L/Ú´DP- /Ú˜«AÏœ¹,

e éu? ¿:u∈V(G),L˜L

÷ v|L

( u) |= k. ·‚Œ±3L

( u) Ú[ k] ƒmïá˜‡V

 .éuz^>uv∈E(G),-:uÚ:vƒm†L

( u) ÚL

( v) ¥ƒ˜˜éAôÚ/

¤ ˜‡š•M

. ·‚Œ±•, ù‡M

- /Údu˜‡L

- /Ú. Ïd, éu?¿ãG,

( G) ≥χ

( 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

:= G−u, ¼êf

: V( G

) →Zde¡ªf‰Ñ

( v) :=







f (v )−1, XJuv ∈E (G );

f (v ), Ù§œ¹.

X J•ª¼êf

´ šK,=é?¿v∈V(G

), Ñkf

( v) ≥0, @o·‚¡T/íØ0ö

Š ´k.XJ·‚Œ±ÏL˜Xk/íØ0öŠ KG¥¤k:,@o·‚¡ãG

´ f-òz.

ã DP-/ÚÚL/Ú˜‡«O´:3L/Ú¥,XJn´óê,@oχ

( C

) = 2, XJn

´ Ûê ,@oχ

( C

) =3. 3DP- /Ú¥, éu¤kn≥3, Ñkχ

( C

) =3. Ïd, ·‚•

Ä ´ÄŒ±?U8/ÚL§5/•0˜ôÚ,χ

( 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.1175014762 A^êÆ?Ð

¶ ——

Ø •0öŠ(G,f,u,w)ãG

:= G−u, ¼êf

: V( G

) →Zde¡ªf‰Ñ

( v) :=







f (v )−1, XJuv ∈E (G ),v 6=w ;

f (v ), Ù§œ¹.

X Jf(u)>f(w)…•ª¼êf

´ šK,@o·‚¡T/íØ•0öŠ´ k.

X J·‚Œ±Ï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 )≤χ

( G) ≤χ

DPP

( G) ≤wd( G)+1 ≤∆( G)+1 .

ù pχ

( 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

∼

∆+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

+2 d−2

¯¢ y²,¦ ^/íØ0Ú/íØ•0öŠ•{Œ±y²A‡š²…þ..1994c,

Thomassen[6] y²¤k²¡ã´5- ŒÀ;2015 c,Dvoˇr´ak ÚPostle[3] y²¤k²¡ã

´ DP-5-Œ/;2021c,BernshteynÚLee[5]JÑfòzÝVg,2grù˜(J?1\r,

¦ ‚y²¤ k²¡ã´4-fòz.

Skrekovski[7] y²Ø¹K

- fªã´5- ŒÀ; 5§Shen[8] <‰Ñ,˜«•{y

² Ø¹K

- fªã´5- ŒÀ;Wang[9] <y²Ø¹K

- fªã´DP-5- Œ/. ·‚\

r T(J§y²Xe½n:

½ n1.4¤kØ¹K

- 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.1175014763 A^êÆ?Ð

¶ ——

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

( v), Ý•d( –•d½–õ•d) :¡•d- :( d

- :½d

−

- :). ÎÒd- ¡,

- ¡, d

−

- ¡•aq½Â. éu¡f∈F, XJf>.þ:Uì^ž^Sv

,...,v

ü §@

o ·‚ PŠf= [v

...v

], ¿…¡f•˜‡( d

( v

) ,d

( v

) ,...,d

( v

) )- ¡. ãG•ÝÚ•

Œ Ý©O•δ(G)=min{d

( v) |v∈V( G) }Ú∆( G)= max{d

( 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«

3 G¥íK:vÚ¤k†Ù'é>ã.

2. Ø¹K

- fªã

² ¡n¿ ©´˜«i\ª² ¡ã,§z‡¡Ñ±˜‡•Ý•3•.,Cqn¿ ©ã

• ´˜ «i\ª²¡ã,Ù¥z‡k.¡±˜ ‡n/•.,Ã.¡(Ü¡)±˜ ‡•..ü‡

ã G

Ú G

 `-Ú´•G=G

… G=G

= K

Wagner ã[14]( „ã1) ˜‡k8 ‡º:,12 ^>3 Kã. 5¿Tã´š²¡ã, Ïd, §

Ø U´²¡ãfã.Ø ¹K

- fª4Œ>ãG•§Ø¹K

- fª, ´éuG¥?¿ü

‡ Øƒº:xÚy,G+xy•¹˜‡ K

- fª.

Figure1. Wagnergraph

ã 1.Wagnerã

DOI:10.12677/aam.2022.1175014764 A^êÆ?Ð

¶ ——

½ n2.1£Wagner[14]¤z‡Ø¹K

- fª4Œ>ãÑŒ±ÏLWagner ãÚ²¡n

¿ ©ã2-Ú†3-ÚØäÊë¤.

½ n2.2[5]G´˜‡–k3‡:²¡ã,Ù¥z‡šÜ¡Ñ´n/,…Ü

¡ ´˜‡k•C,C>.þ:Uì^ž^Sv

,...,v

ü .½Âf:V(G)\{v

}→ Z

•

f (u ) :=







2 −|N

( u) ∩{v

}| ,XJu∈ V(C);

4 −|N

( u) ∩{v

}| ,Ù§œ¹.

@ oG−v

− v

´ /(V(G)\{v

} )-f-fòz0.

Ú n2.3G´˜‡Cqn¿©ã,f•G˜‡~¼ê,¿…é?¿v∈V(G)þ÷

v f(u)=4−|N

( u) ∩{v

}| .bH•G˜‡ÓuK

 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

Ú V(H) = (u,v,w).

œ ¹1µHØ´G˜‡©l3-.duG´˜‡Cqn¿©ã,·‚Œ±-#xÑTã,

¦ H´ GÜ¡.5¿G

= G−w•´Cqn¿©ã, k‰Hþ:wüS, XJx

Ú w´ƒ,-f

( x) = 3 −|N

( x) ∩{u,v}|. Ù¦œ¹e, Ñkf

= 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

L «¤k:Ú> 3HSÜ ½Hþ˜‡ã,G

« ¤k:Ú>3HÜ½Hþ˜‡ã.aquþã y²,·‚Œ±3HSλÄ:þ?U

¤ G

 ˜‡S,Ó?U¤G

 ˜‡S.(Üüö,·‚ G ˜‡S§¦ 3ù‡

S e,Œ±ÏL˜Xk /íØ0Ú/íØ•0öŠKG¥¤k:.ÏdG´f-fò

z ,Ún2.3y..

Ú n2.4G´˜‡¹k4Œ>Ø¹K

- fªã, …é?¿u∈V( G), f( u)=4 −

| N

( u) ∩{v

}| .bH´G˜‡ÓuK

½ öK

 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)|Š8B5y²TÚn,XJG´Cqn¿©ã,@où‡(JŒ±†

l Ún2.3.XJH=y

, ·‚Œ±by

 u˜‡3-¡[y

], @ow,3HS

 Ä:þŒ±?U¤G

= [ y

] ˜‡S. lT¯KŒ±{z•Ún2.3 œ¹.

X JG´Wagnerã,@ow,G´f-fòz.

b GQ Ø´˜‡²¡n¿©•Ø´Wagnerã,3ù«œ¹e,dWagner½n[14]Œ±

Ñ G=G

, Ù¥G

´ Gfã,÷vG

' K

½ öK

. w,, H⊆G

½ G

. Ø”

DOI:10.12677/aam.2022.1175014765 A^êÆ?Ð

¶ ——

H ⊆G

, 3G

þ A^8Bb,3HSÄ:þ Œ±?U¤G

 ˜‡S,ù)G

 ˜‡S.3G

þ A^8Bb,Œ±òH3G

 SÄ:þ?U¤G

˜ ‡S.ù

Ò )G˜‡S,…3ù‡Se,Œ±ÏL˜Xk/íØ0Ú/íØ•0öŠ

K G¥¤k: ,ÏdG´f-fòz .Ún2.4y..

½ n1.4¤kØ¹K

- fªã´4- fòz.

y ²duz‡Ø¹K

- fªã´˜‡¹k4Œ>Ø¹K

- fªã)¤fã, Ïd, ·‚

• I‡y ²¹k4Œ>Ø¹K

- 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

´ d˜

‡ 5-Ú˜‡ ƒ3-|¤ã.=V(F

) = {v

} ,Ù¥v

/ ¤

 ˜‡6-,v

• ˜^u,-H´G˜‡fã,XJH†F

Ó ,¿…éu?¿:vÑ÷v

( v) = 4, @oH¡•F

f ã.

Ú n4.2[10]G´˜‡Ø¹4-…Ø¹ƒ3-²¡ã,XJδ(G)=4,@oG•¹˜

‡ F

- 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

- fãH. -G

:= G−V( H),

f ≤3´V (G )˜‡~¼ê.ŠâG 45,·‚Œ±ÏL˜Xk/íØ0Ú/í

Ø •0öŠK(G

,f )¥¤k:.y3·‚•ÄãH ,Äk/íØv

 •v

0 ,,U

ì v

 ^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.1175014766 A^êÆ?Ð

¶ ——

• (b)G¥vkÓu4-†3-ƒfã;

• (c)GØ´3-fòz;

• (d)Gz‡fãG

´ 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.1 y..

 e5,·‚½ÂA‡ØÓ5-¡.f´G˜‡5-¡.

• (a)XJf´˜‡(4,4,4,4,4)-¡,@o·‚¡f•5-¡.XJf†˜‡3-¡f

=[ vv

v ]ƒ

 ,Ùú>•v

, @o·‚¡v´f˜‡. Ó, ¡f¡•v˜‡®.( „ã2 ¥F

• (b)XJf´˜‡(5

, 4, 4, 4, 4)-¡,¿…f †o‡3-¡Ú˜‡4

- ¡ƒ, ¿…4

- ¡†fþ

- :'é, @o·‚¡f•˜‡€5- ¡.( „ã2 ¥F

• (c)XJf´˜‡(5

, 4, 4, 4, 4)-¡,¿…f †Ê‡3-¡ƒ,@o·‚¡f •˜‡AÏ5-¡.Ó

ž ,·‚¡fþ5

- :•˜‡AÏº:.( „ã2 ¥F

Figure2. Deﬁnitionofdiﬀerent5-faces

ã 2.ØÓ5-¡½Â

I 54.2

• (1)˜‡AÏº:–'é˜‡AÏ5-¡,˜‡AÏ5-¡TÐ†˜‡AÏº:'é;

• (2)XJ3˜‡5-¡fþ•3ü‡5

- :, @ofQØ´˜‡AÏ¡•Ø´˜‡€¡.

Ú n4.3z‡Ñ´˜‡5

- :.

y ²f=[v

] ´˜‡5- ¡, z´f˜‡. dÚn4.1 Œ•G¥Ø•3

−

- :, Ïd·‚Œ±bd

( z)=4. Ø”˜„5, ·‚Œ±bz†v

Ú v

ƒ .G[S]•

S ={z,v

} pGfã.•ÄGfãG

:= G−V( G[ S]). Šâ(d), G

´ 3-f

ò z.,·‚•ÄG[S],Äk/íØv

 •z0,,Uìv

,z ^S/íØ0•{

DOI:10.12677/aam.2022.1175014767 A^êÆ?Ð

¶ ——

: .dL§¥/íØ•0Ú/íØ0öŠ´k ,¤±G[S]´3-fòz .G•´3-fò

z .ù†(c)´gñ,Ïdd

( z) ≥5. Ún4.3 y..

ä ó4.4v´G˜‡5

- :, Ke¡(Ø¤á:

• (1)v•õ'é

d (v )

‡ 3-¡;¿…

• (2)XJv†t‡3-¡'é…2t

( 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

Ú ˜‡3-¡f

' é,

¿ …f

Ú f

ƒ ,@ovvkuf

 ®.

y ²f

= [ vv

v ]´˜‡AÏ5-¡½ö€5-¡.ŠâAÏ5-¡½ö€5-¡½Â,–

 ko‡3-¡†f

ƒ .bf

= [ vv

v ],…f

† f

ƒ („ã3).|^‡y{,bvk˜‡

® f

= [ v

] †f

ƒ ,Ù¥v

• §‚ú>,@ov

´ f

 ˜‡.,,v

´ ˜

‡ 4-:,ù†Ún4.3gñ.Ún4.5y..

Figure3. IllustrationofLemma4.5

ã 3.Ún4.5«¿ã

Ú n4.6f

Ú f

´ ü‡€5-¡,@o§‚ØU†˜^ú>vv

 ~ƒ,Ù¥ v´f

Ú f

þ 5

- :.

y ²bf

Ú f

´ ü‡€5-¡,§‚´ ~ƒ,§‚k˜‡ú5

- :vÚ˜^ú

> vv

( „ã4). Ï•f

Ú f

Ñ ´€5-¡,@ov

´ ˜‡4-:,f

=[ v

] Úf

=[ v

]

´ ü‡3-¡.Ïd,f

Ú f

´ ƒ,ù†(b)gñ,Ïdb´ †Ø.Ún4.6y..

 =£Äk,·‚½Â˜‡Xã5¤«˜‡..3ã5¥,xÚº:Ýê–´'é>

 êþ,çÚº:Ý ê u'é> êþ.ùÚº: v´˜‡AÏ5-: ,§†˜‡AÏ5-¡f

˜ ‡€5-¡f

Ú ˜‡5-¡f

' é,…÷v±e^‡:

• f

Q Ø´AÏ5-¡•Ø´€5-¡;¿…

• f

† ˜‡AÏ5-:v'é,…v† ˜‡€5-¡f

' é;¿…

• f

† f

 ~ƒ.

DOI:10.12677/aam.2022.1175014768 A^êÆ?Ð

¶ ——

Figure4. IllustrationofLemma4.6

ã 4.Ún4.6«¿ã

Figure5. Special5-vertexand

incident5-faces

ã 5.AÏ5-:†'é5-¡

· ‚¡F

• f

 8Ü,=F

´ d¤k5-¡|¤8Ü,§‚†f

k ƒÓ5Ÿ.·‚¡ù

˜ ‡AÏ5-:v•«¡AÏ5-:.

I 54.7w•f

 ˜‡º: ,Xã5¤«.XJd

( w)= 4, @oŠâ(b), w•õ'é˜‡

3- ¡.

d î.úª|V|−|E|+|F|= 2Úúª

v ∈V

( v) = 2 |E|=

f ∈F

( f). ·‚Œ±Ñ

v ∈V

(2 d

( v) −6)+

f ∈F

( d

( f) −6) = −12 .

y 3·‚éz‡x∈V

F ½Â˜‡Ð©-ch (x ),éz‡v ∈V ,ch (v )=2d

( v) −6,

z ‡f∈F,ch(f)=2d

( f) −6. ·‚òO·=£5K. du=£L§¥, oŠ

´ ½,XJ·‚òÐ© Šch(x)UC••ªŠch

( x), ¦éuz‡x∈V

F ,Ñ÷v

( x) ≥0, @o

0 ≤

x ∈V ∪F

ch (x ) =

x ∈V ∪F

( x) = −12 .

ù ò´˜‡gñ.ù ¿›X½n¥‡~Ø•3 ,Ïd½n¤á.

DOI:10.12677/aam.2022.1175014769 A^êÆ?Ð

¶ ——

· ‚^c(v→f)L«lv=£‰fŠ,Ù¥v∈V(G)Úf∈F(G).

 =£L§X e:

• (R1)XJv´˜‡4

- :…f´§'é3- ¡, @oc( v→f) = 1;

• (R2)XJv´˜‡4

- :…f´§'é4- ¡, @oc( v→f) =

;

• (R3)XJv´˜‡–õ†˜‡3-¡'é4-:,f´˜‡†v'é5-¡,@oc(v→ f) =

(

, XJv TÐ†˜‡3-¡Ú˜‡4-¡'é;

, Ù¦œ¹.

• (R4)ŠâIP4.2(1),˜‡AÏ5-¡TÐ†˜‡AÏº:'é.v´˜‡AÏ5

- :, f´˜

‡ †v'é5-¡,@oc(v→f) =











1 ,XJf´AÏ5- ¡;

, XJd

( v) = 5 …f´€5- ¡( „ã5 ¥f

);

, XJd

( v) = 5, v´«¡, …f∈F

( „ã5 ¥f

• (R5)XJvØ´˜‡AÏ5-:½6

- :, …f´˜‡†v'é€5- ¡, @oc( v→f) =

;

• (R6)XJv´f˜‡,@oc(v→ f) =

;

• (R7)XJv´6

- :½Ø´˜‡AÏ5- :, ½ö´˜‡Ø†˜‡€5- ¡'éAÏ5- :, …X

J fØ´˜‡AÏ5-¡½ö€5-¡,Ù¥f†v' é,@oc(v→f) =

‡ ¤½n1.6y²,„I‡ u V

F ¥z‡ƒ•ªŠ´Ä´šK,e¡ü^ä

ó òéd?1 `².

ä ó4.8éu¤kv∈V(G),ch

( v) ≥0.

y ²ŠâÚn4.1,G¥Ø•33

−

- :, Ïd·‚I‡3e¡•Ä4

- :.

œ ¹1µd

( v) = 4.

3ù «œ¹e,·‚kch(v) =4×2−6 = 2.ŠâÚn4.3,vvk?Û®.XJv†ü‡3-¡

' é,@oŠâR1,ch

( v) = ch( v) −2 ×1 = 0.

X JvTÐ†˜‡3-¡'é,@oŠâ(b)Œ•,v•õ†˜‡4-¡'é.bv†˜‡4-¡'

é ,@o§•õ†ü ‡5-¡'é .ŠâR1,R2ÚR3,ch

( v) ≥ch( v) −1 −

−

× 2 = 0.ÄK,v•

õ 'én‡5-¡.ŠâR1ÚR3,ch

( v) ≥ch( v) −1 −

× 3>0.

X JvØ†? Û3-¡'é,@oŠâR2ÚR3,ch

( v) ≥ch( v) −

× 4 = 0.

œ ¹2µd

( 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-¡'é.ŠâÚ

n 4.5,vvk®.XJv†˜‡€5-¡'é ,ŠâÚn 4.6Œ•,v•õ†˜‡€5-¡'é .Ïd·‚

DOI:10.12677/aam.2022.1175014770 A^êÆ?Ð

¶ ——

Œ ±lR1ÚR4¥ch

( v) ≥ch( v) −1 ×2 −1 −

−

= 0. ÄKvØ†?Û€5- ¡'é, Šâ

R1,R4 ÚR7, ch

( v) ≥ch( v) −1 ×2 −1 −

× 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, ·‚Œ±Ñ

( v) >ch( v) −1 ×2 −1 −

−

× 2>0.

• XJvTÐ†˜‡3-¡'é,@oŠâ€5-¡½Â,v•õ†ü‡€5-¡'é,ÏdŠâR1,

R4,R6 ÚR7, ch

( v) >ch( v) −1 −

−

× 2−

× 2>0.

• XJvØ†?Û3-¡'é§@ovØ†?Û€5-¡'é.ŠâR2ÚR7,ch

( v) ≥ch( v) −

× 5>

œ ¹3µd

( 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

( v) ≥ch( v) −3 −3 = 0. ÄKv•õ'éü‡AÏ5- ¡. ŠâÚn4.5 Œ•,

v vk?Û®.ŠâR1,R4ÚR5,ch

( v) ≥ch( v) −3 −2 −

> 0.

• bv•õ†ü‡3-¡'é,@oŠâÚn4.4(2)Œ•,v•õ†˜‡AÏ5-¡'é.XJv†

˜ ‡AÏ5-¡'é,@oŠâR1,R4,R5ÚR6Œ,ch

( v) >ch( v) −2(1+

) −1 −

× 3>0.

Ä KŠâÚn4.6,v•õ†ü‡€5-¡'é.Ïd,ŠâR1,R4,R5,R6ÚR7,·‚Œ±Ñ

( v) >ch( v) −2(1+

) −

× 2−

× 2>0.

œ ¹4µd

( v) = 7.

3ù «œ¹e§ch(v)=2×7−6 =8.ŠâÚn4.4,v•õ'én‡3-¡,•õ'éü‡AÏ

5- ¡. ŠâR1,R4,R5 ÚR6, •ªŠ••ch

( v) >ch( v) −3(1+

) −2 −

× 2>0.

œ ¹5µd

( v) = k≥8.

5 ¿ch(v)=2k−6.ŠâÚn4.4,v• õ'é

d (v )

‡ 3-¡,•õ'é

d (v )

‡ AÏ5-¡.

Š âR1,R4ÚR6,Œ±Ñch

( v) ≥ch( v) −(1+

) ×

d (v )

− 1×

d (v )

> 0.

ä ó4.8y..

ä ó4.9éu¤kf∈F(G),ch

( f) ≥0.

y ²f´G˜‡¡,Ï•G´{üã,¤±Gvk‚Úõ->.d

( f) ≥3. XJ

( f) ≥6, @ofQØlO?Š, •Ø•=ÑŠ. Ïd§ch

( f) = ch( f) = d

( f) −6 ≥0.

X Jd

( f)=3, @oŠâR1, †f'éz‡:=1 ‰f. Ïd, ·‚Œ±ch

( f)=

ch (f ) +3×1=d

( f) −6+3=0. XJd

( f)=4, @oŠâR2, †f'éz‡:=

‰

f ,Ïd•ªŠch

( f)= ch( f)+ 4 ×

= d

( f) −6 +2=0. e5·‚bd

( f)=5, @o

ch (f ) = 5−6 =−1.

DOI:10.12677/aam.2022.1175014771 A^êÆ?Ð

¶ ——

œ ¹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

( f) ≥−1+

× (5− t)+

× (t+1) =

9 −t

> 0.

œ ¹2µf´˜‡(5

, 4, 4, 4, 4)-¡.

^ vL«5

- :, XJf´˜‡AÏ5- ¡, @oŠâR4, ch

( 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,

( f) ≥−1 +

=0. ÄKfØ´€5- ¡, @of∈F

, v´˜‡«¡AÏ5- :. 5¿

 ã5¥ fÒ´f

. Ïd, ŠâI54.7, f–†ü‡4- :'é, …ùü‡4- :•õ'é˜‡

3- ¡, …ØÓž'é˜‡3- ¡Ú˜‡4- ¡. ŠâR3,R4 ÚR7, ch

( f) ≥1+

= 0.

• ÄK,v´˜‡6

- :, ½övØ´˜‡AÏ5- :, ½öv´˜‡AÏ5- :…vØ†˜‡€5- ¡

' é.XJ f´€5-¡,@o•3˜‡†f' é4-:,¿…ù‡4-:•õ' é˜‡3-¡.Š

â R3ÚR5,ch

( v) ≥−1+

=0. XJfØ´€5- ¡, @of–'éü‡4

- :, ¿…

ù ü‡4

- :•õ'é˜‡3- ¡. ŠâR3 ÚR7, ch

( f) ≥−1+

× 2+

= 0.

œ ¹3µfþ–•3ü‡5

- :.

l I54.2(2)Œ•,fQØ´AÏ5-¡•Ø´€5-¡.

• XJf∈ F

, @oŠâI54.7,R3,R4 ÚR7, ch

( f) ≥−1+

× 2+

= 0.

• XJf/∈F

, =fØ†˜‡AÏ5- :'é, Ù¥ù‡5- :3˜‡AÏ5- ¡þ…†˜‡€5- ¡

' é.ŠâR7,ch

( f) ≥−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.1175014772 A^êÆ?Ð

¶ ——

[4]Bernshteyn,A.andKostochka,A.(2018)OnDiﬀerencesbetweenDP-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)Choosabilityof K

-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-Choosabilityof K

-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)ASuﬃcientConditionforDP-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

SpeciﬁcLengths. EuropeanJournalofCombinatorics,23,377-388.

https://doi.org/10.1006/eujc.2002.0570

DOI:10.12677/aam.2022.1175014773 A^êÆ?Ð