不含相邻 5--圈的平面图的均匀染色 Equitable Coloring of Planar Graphs without Adjacent 5--Cycles

doi:10.12677/AAM.2023.123105

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

期刊菜单

文章导航

AdvancesinAppliedMathematicsA^êÆ?Ð,2023,12(3),1035-1044

PublishedOnlineMarch2023inHans.https://www.hanspub.org/journal/aam

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

Ø¹ƒ5

−

-²¡ãþ!/Ú

ÇÇÇuuu$$$

∗

§§§‘‘‘ûûû

úô“‰ŒÆ§êÆ‰ÆÆ§úô7u

ÂvFÏµ2023c213F¶¹^FÏµ2023c39F¶uÙFÏµ2023c316F

Á‡

ãG˜‡þ!k-/Ú´•G˜‡~k-:/Ú…÷v?¿ü‡Úaº:êƒýéŠ

–õ•1 "eG•3˜‡þ!k-/Ú§K¡G´þ!k-Œ/"©ò$^=£•{y²µ

Ø¹ƒ5

−

-²¡ã´þ!k-Œ/§Ù¥k≥max{∆(G),5}…∆(G) ´ãG•ŒÝ"

'…c

þ!k-/Ú§²¡ã§

EquitableColoringofPlanarGraphs

withoutAdjacent5

−

-Cycles

XianxiWu

∗

,DanjunHuang

SchoolofMathematicalSciences,ZhejiangNormalUniversity,JinhuaZhejiang

Received:Feb.13

,2023;accepted:Mar.9

,2023;published:Mar.16

,2023

Abstract

Anequitablek-coloringofa graphGisapropervertexcoloringsuchthatthediﬀerence

∗ÏÕŠö"

©ÙÚ^:Çu$,‘û.Ø¹ƒ5

−

-²¡ãþ!/Ú[J].A^êÆ?Ð,2023,12(3):1035-1044.

DOI:10.12677/aam.2023.123105

Çu$§‘û

in theorder of any twocolor classes isat most one.The graphGis saidto beequitably

k-colorableifGhasanequitablek-coloring.Inthispaper,wewillprovethatevery

planargraphwithoutadjacent5

−

-cyclesisequitablyk-colorablefork≥max{∆(G),5},

where∆(G)isthemaximumdegreeofG.

Keywords

Equitablek-Coloring,PlanarGraph,Cycle

2023byauthor(s)andHansPublishersInc.

This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).

http://creativecommons.org/licenses/by/4.0/

1.Úó

3©¥,·‚••ÄÃ•!k•{üã.éu˜‡‰½ãG,·‚^V(G),E(G),|G|,

δ(G) Ú∆(G) ({•∆) 5©OL«ãG:8,>8,ê,•ÝÚ•ŒÝ.XJãGŒ±x

3îAp²¡þ¿…÷v?¿2^>•3à:?ƒ,K¡G•Œ²¡ã.ãGù«AÏ²

¡x{¡•²¡ã.·‚^F(G) 5L«²¡ãG¡8.x∈V(G) ∪F(G),^d(x) L«ãG

¥:(½¡) xÝ.XJ˜‡:v÷vd(v)=k(d(v)≥k½d(v)≤k),@ o¡:v•k-:(k

½k

−

-:).aq/,·‚Œ±½Âk-¡, k

-¡½k

−

-¡.éuv∈V(G),^N(v) L«†:vƒ

¤kº:¤8Ü.w,,



N(v)



=d(v).éuf∈F(G),ev

,···,v

´¡f>.þ

:(#Nº:k-E),KPf=[v

···v

].XJ˜‡k-¡f=[v

···v

] ÷vd(v

)=d

,Ù¥

i=1,2,···,k,Kf•(d

,···,d

)-¡.·‚^n

(f),n

(v),f

(v)©OL«†¡f'éi-:

‡ê,†:vƒi-:‡ê,†:v'éi-¡‡ê.

ãG˜‡~k-:/Ú´•˜‡Nφ: V(G) →{1,2,···,k}, ¦é?¿2‡ƒ:x

ÚyÑkφ(x)6= φ(y).ãG:Úê´¦Gk˜‡~k-:/Ú•êk,PŠχ(G).é

uãG˜‡k-:/Úφ,^V

(1≤i≤k) L«ãG¥/ôÚiº:| ¤8Ü.Kz‡V

(1 ≤i≤k) Ñ´˜‡Õá8.eé?¿i,j∈{1,2,···,k}Ñk



|−|V



≤1,K¡φ´ãG˜

‡þ!k-/Ú,½¡ãG´þ!k-Œ/.ãGþ!Úê´¦Gk˜‡þ!k-/Ú•

êk,PŠχ

(G).w,,χ

(G) ≥χ(G),…ØªŒ±î‚¤á.

þ!/ÚVg´dMeyer[1]31973 cJÑ,Óž,¦„JÑ±eßŽ.

ßŽ1[1]eG´˜‡ëÏã,…GQØ´Û•Ø´ã,Kχ

(G) ≤∆.

þ!/ÚïÄŒJˆ1964c.Erd˝os[2]JÑXeßŽ.

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

Çu$§‘û

ßŽ2[2]é?¿k≥∆,?¿˜‡•ŒÝ•∆ ãÑ´þ!(k+1)-Œ/.

ßŽ231970cHajnalÚSzemer´edi[3]¤y¢.2010c,Kierstead ÚKostochka[4]A^Ž

{©ÛéßŽ2‰Ñ˜‡#Û{áy².1994c,Chen,Lih ÚWu[5]?˜ÚJÑ±eßŽ.

ßŽ3[5]eG´˜‡ëÏã,…GQØ´K

2m+1

, •Ø´K

2m+1,2m+1

(m≥1),KG

´þ!∆-Œ/.

Chen,Lih ÚWu[5]„y²ßŽ3é∆≤3 ã¤á.Kierstead ÚKostochka[6]òd(

JU?∆≤4.Chen,Lih[7]ÚLih,Wu[8]©Oy²ßŽ3éä!Üã¤á.Wang

ÚZhang[9]y²ßŽ3 é‚ã¤á.Kostochka[10]y²ßŽ3é²¡ã¤á,¿…„Ú

Nakprasit[11]˜åy²ßŽ3 é∆ ≥14d+1d-òzã¤á.1998c,YapÚZhang[12]y²

ßŽ3 é∆≥13 ²¡ã¤á.Nakprasit[13]ò©z[12](JU?∆ ≥9.Ïd,²¡ã

x••e5 ≤∆ ≤8œ¹„vk)û.

2008 c,Zhu ÚBu[14]y²∆≥7 …Ø¹4-Ú5-²¡ã´þ!∆-Œ/.2014 c,

Wang ÚGui[15]?˜Úy²T(Øé5 ≤∆ ≤6 …Ø¹4-Ú5-²¡ã•¤á.ddÑ

z˜‡Ø¹4-Ú5-²¡ãÑ´þ!∆-Œ/.2015 c,Zhu,Bu ÚMin[16]y²Ø¹

5-Úu4-²¡ã´þ!k-Œ/,Ù¥k≥max{∆,8}.2019 c,Dong ÚWu[17]y²Ø¹

u4-Úu6-²¡ã´þ!k-Œ/,Ù¥k≥max{∆,7}.

©$^=£•{y²Ø¹ƒ5

−

-²¡ã´þ!k-Œ/,Ù¥k≥max{∆,5}.(

Ü©z[5]Ú©z[6](JŒ•,Ø¹ƒ5

−

-²¡ã÷vßŽ3.

2.(Ún

Ún1[14]-S={v

,···,v

}⊆V(G), Ù¥v

,···,v

´ãG¥k‡ØÓ:.e

G−S´þ!k-Œ/,…é?¿1 ≤i≤k,Ñk|N

)−S|≤k−i,KG´þ!k-Œ/.

Ún2[18]3-Ú5-Øƒ²¡ã´3-òz.

Ún3[3,4]ék≥∆+1,?¿˜‡•ŒÝ•∆ ãÑ´þ!k-Œ/.

Ún4eG´˜‡|G|≥5 …Ø¹ƒ5

−

-ëÏ²¡ã,KG•¹ã1¥fã/ƒ˜.

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

Çu$§‘û

Figure1.FigureH

∼H

inLemma4

ã1.Ún4¥fã/H

∼H

ã1z‡f ã/Ñ÷v:(1)¢%:ÝêXã¤«;(2)˜%:ÝêØAO`²Œáu

«m[d,∆] ¥?Ûê,Ù¥d•ã¥˜%:Ýê;(3)z˜‡fã/¥,IÒ•x

k−1

k−2

:Ø¬ƒp-Ü;(4)ã¥†4-¡ƒ'é:^SŒ±p†;(5)H

¥†5-¡ƒ'é:^

SŒ±p†.

y²æ^‡y{,bÚn4 Ø¤á.-G´˜‡‡~ã.=G´˜‡|G|≥5 …Ø¹ƒ

−

-ëÏ²¡ã,§Ø¹fã/H

∼H

¥?Û˜‡.Ïd,Gk5ŸP1.

P1.f

(v)+f

(v) ≤b

d(v )

·‚$^=£•{5íÑgñ.Äk,3V(G) ∪F(G)þ½Â˜‡Ð©¼êw:é

v∈V(G),-w(v) = 2d(v)−6;éf∈F(G),-w(f) = d(f)−6.Šâî.úª|V(G)|−|E(G)|+

|F(G)|= 2ÚºÃ½n

v ∈V(G)

d(v) =

f∈F(G)

d(f) = 2|E(G)|,k

x∈V(G)∪F(G)

w(x) =

v ∈V(G)

(2d(v)−6)+

f∈F(G)

(d(f)−6) = −12.

X,·‚‰Ñ˜=£5K,¿…Uìù@5Kéã¥:Ú¡-#©.=£L§

(å,¬˜‡#¼êw

,¿…=£L§¥¤k:Ú¡Ú±ØC.

éux,y∈V(G)∪F(G),·‚^τ(x→y) L«x=‰y.½ÂXe=£5K:

R1.v∈V(G)…f´†:v'é3-¡.

R1.1 bd(v)=4.f´(3,4,4)-¡ž,-τ(v→f)=

;f´(4,5

)-¡ž,-

τ(v→f) = 0;ÄK,-τ(v→f) = 1.

R1.2bd(v) = k≥5.f´(3

−

,k)-¡ž,-τ(v→f)=3;f´(3

−

,4,k)-¡ž,-

τ(v→f) = 2;f´(4

−

,k)-¡ž,-τ(v→f) =

;ÄK,-τ(v→f) = 1.

R2.v∈V(G)…f´†:v'é4-¡.

R2.1bd(v)=4.f´(3,4,4,4)-¡ž,-τ(v→f)=

;f´(2,4,4,5

)-¡ž,-

τ(v→f) =

;f´(2,4,5

)-¡ž,-τ(v→f) = 0;ÄK,-τ(v→f) =

R2.2bd(v) = k≥5.f´(2,4,4,k)-¡ž,-τ(v→f) =

;ÄK,-τ(v→f) = 1.

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

Çu$§‘û

R3.v∈V(G)…f´†:v'é5-¡.

R3.1bd(v) = 4.f'é2-:ž,-τ(v→f) =

;ÄK,-τ(v→f) =

R3.2bd(v) ≥5,-τ(v→f) =

R4.z‡4

-:‰ƒ2-:=1.

dÚn2Œ•,δ(G) ≤3.Šâδ(G) Š,·‚©±eA«œ¹?Øµ

œ¹1δ(G) = 3.

dž‰1=£5K•R1 ∼R3.

Ï•GØ¹fã/H

∼H

,¤±ãGäkXe5Ÿ.

äó1.1G¥3-¡Ñ´(3,3,5

)-¡,(3,4

)-¡,½(4

)-¡.

äó1.2G¥4-¡Ñ´(3,3,5

)-¡,(3,4

)-¡,½(4

)-¡.

äó1.3G¥5-¡Ñ´(3

)-¡.

e¡·‚ÏLü‡äó5y²é∀x∈V(G)∪F(G),kw

(x) ≥0.

äó1.4∀v∈V(G),kw

(v) ≥0.

y²bd(v) =k.-v

,···,v

´v:…3²¡þ•^ž••ü.-f

´±vv

i+1

•>.>¡,Ù¥1 ≤i≤k…v

k+1

= v

bk= 3.Kw

(v) = w(v) = 0.

bk= 4.Kw(v) = 2.dP1•,f

(v)+f

(v) ≤2.ef

(v) = 2,Kf

(v) = f

(v) = 0.

dGØ¹H

•vØ†(3,4,4)-¡'é.dR1§w

(v)≥2−2×1=0.ef

(v)=1,K

(v)+f

(v)≤1.ev†(3,4,4)-¡'é,Ø”•f

.dGØ¹H

•d(v

)≥5 …d(v

)≥5.

ÏdvØ†(3,4,4,4)-¡'é.dR1∼R3,w

(v)≥2 −

−

=0.evØ†(3,4,4)-¡'

é,dR1∼R3,w

(v)≥2 −1−

.ef

(v)=0,Kf

(v)+f

(v)≤2.dR2∼R3,

(v) ≥2−2×

bk= 5, Kw(v) = 4.dP1•,f

(v)+f

(v) ≤2.ef

(v) = 2,Kf

(v) = f

(v) = 0.

ev†(3,3,5)-¡'é,Ø”•f

.dGØ¹H

•d(v

)≥5(i∈{3,4,5}).K†v'é,

˜‡3-¡7•(5,5

)-¡.dR1§w

(v)≥4 −3 −1=0.evØ†(3,3,5)-¡'é,dR1,

(v) ≥4−2×2=0.ef

(v) =1,Kf

(v)+f

(v) ≤1.dR1∼R3,w

(v) ≥4−3−1=0.e

(v) = 0,Kf

(v)+f

(v) ≤2.dR2 ∼R3,w

(v) ≥4−2×1 = 2.

bk≥6,Kw(v)=2k−6.dP1 •, f

(v)+ f

(v)≤b

c.ev†(3,3,k)-¡'é,

Ø”•f

.dGØ¹H

•d(v

) ≥4(i∈{3,4,···,k}).†v'éÙ¦3-¡7•(k,4

)-¡.

dR1 ∼R3,w

(v) ≥2k−6−3−

c−1)≥2k−

−

k−

≥0.evØ†(3,3,k)-¡'

é,KdR1 ∼R3,w

(v) ≥2k−6−2b

c≥2k−6−2×

= k−6 ≥0.t

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

Çu$§‘û

äó1.5éz‡f∈F(G) Ñkw

(f) ≥0.

y²bd(f)=3.Kw(f)=−3.däó1.1•,f´(3,3,5

)-¡,(3,4

)-¡,½

)-¡.ef´(3,3,5

)-¡,dR1,w

(f)≥−3+3=0.ef´(3,4,4)-¡,dR1,

(f) ≥−3+2×

= 0.ef´(3,4,5

)- ¡,dR1,w

(f) ≥−3+1+2 = 0.ef´(3,5

)-¡,

dR1,w

(f)≥−3 + 2 ×

=0.ef´(4,4,4

)-¡,dR1,w

(f)≥−3 + 3 ×1=0.ef´

(4,5

)-¡, dR1, w

(f) ≥−3+2×

= 0.ef´(5

)-¡, dR1, w

(f) ≥−3+3×1 = 0.

bd(f)=4.Kw(f)=−2.däó1.2•,f´(3,3,5

)-¡,(3,4

)-¡,½

)-¡.ef´(3,3,5

)-¡,dR2,w

(f)≥−2+2×1=0.ef´(3,4,4,4)-¡,

dR2,w

(f) ≥−2+3×

= 0.ef´(3,4

)-¡,dR2,w

(f) ≥−2+2×

+1 = 0.ef

´(4

)-¡,dR2,w

(f) ≥−2+4×

= 0.

bd(f)=5.Kw(f)=−1.däó1.3•,f´(3

)-¡.dR3,w

(f)≥

−1+2×

= 0.

bd(f) ≥6.Kw

(f) = w(f) ≥0.t

nþ?ØŒ•,∀x∈V(G)∪F(G),Ñkw

(x)≥0.Ïd,−12=

x∈V(G)∪F(G)

w(x)=

x∈V(G)∪F(G)

(x) ≥0,gñ.Ïd,‡~Ø•3,=Ún4 ¤á.

œ¹2δ(G) = 2,…G¥–õ•32‡2-:.

dž‰1=£5KÓœ¹1.

duãGØ¹kfã/H

∼H

,¤±ãGäkXe5Ÿ.

äó2.1G¥†2-:'é3-¡´(2,2

)-¡.

äó2.2G¥†2-:'é4-¡´(2,3

−

)-¡,(2,4

)-¡.

äó2.3G¥†2-:'é5-¡´(2,3

−

)-¡,(2,4

)-¡.

Ø2-:9Ù'é¡,éz‡x∈V(G)∪F(G),Óœ ¹1aqŒyw

(x)≥0.éu2-:'

é¡,kXeäó.

äó2.4éz‡2-:'é¡f∈F(G) Ñkw

(f) ≥0.

bd(f)=3,Kw(f)=−3.däó2.1 •,f´(2,2

)-¡.ef•(2,3

−

)-¡,dR1,

(f) ≥−3+3 = 0.ef•(2,4,5

)-¡,dR1,w

(f) ≥−3+1+2 = 0.ef•(2,5

)-¡,d

R1,w

(f) ≥−3+2×

= 0.

bd(f)=4,Kw(f)=−2.däó2.2•,f´(2,3

−

)-¡,(2,4

)-¡.e

f•(2,3

−

)-¡,dR2,w

(f)≥−2+2×1=0.ef•(2,4,4,5

)-¡,dR2,w

(f)≥

−2+2×

= 0.ef•(2,4

)-¡,dR2,w

(f) ≥−2+2×1 = 0.

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

Çu$§‘û

bd(f)= 5,Kw(f)=−1.däó2.3 •,f´(2,3

−

)-¡,(2,4

)-¡.

ef•(2,3

−

)-¡,dR3,w

(f) ≥−1+3×

.ef•(2,4

)-¡,dR3,

(f) ≥−1+4×

= 0.t

nþ?ØŒ•, Ø2-:,∀x∈V(G)∪F(G),Ñkw

(x) ≥0.Ïd, −12 =

x∈V(G)∪F(G)

w(x) =

x∈V(G)∪F(G)

(x) ≥2×(−2) = (−4),gñ.Ïd,‡~Ø•3,=Ún4 ¤á.

œ¹3δ(G) = 2,…G¥–•33‡2-:.

dž‰1=£5K•R1 ∼R4.

duGØ¹kfã/H

∼H

,KGäkXe5Ÿ.

äó3.1†2-:'é3-¡•(2,3

)-¡.

äó3.2†2-:'é4-¡•(2,3,5

)-¡½(2,4

)-¡.

äó3.3†2-:'é5-¡•(2,3,5

)-¡½(2,4

)-¡.

äó3.4ü‡2-:Øƒ.

äó3.5?Û3

-:v–õ†1 ‡2-:.

äó3.6v´†2-:k-:(k≥4),KvØ†(3

−

,k)-¡'é.

v´2-:,e:v†3-:ƒ,K¡:v•AÏ2-:.ÄK,¡:v•ÊÏ2-:.dGØ¹f

ã/H

,Keäó¤á.

äó3.7ã¥–õ•3˜‡AÏ2-:.

e¡·‚ÏLü‡äó5y²

x∈V(G)∪F(G)

(x) ≥−2.

äó3.8éuAÏ2-:v,w

(v) ≥−2;éuÊÏ2-:½3

-:v,w

(v) ≥0.

y²bd(v) =k.-v

,···,v

´vØ…3²¡þ•^ž••ü.-f

´±vv

i+1

•>.>¡,Ù¥1 ≤i≤k…v

k+1

= v

bk=2,Kw(v)=−2.ev•ÊÏ2-:,Kn

(v)≥2.dR4 ,w

(v)≥−2+2×1=0.

ev•AÏ2-:,Kw

(v) ≥−2.bk= 3,Kw

(v) = w(v) = 0.¤±e¡•Äk≥4.däó3.5

•,n

(v) ≤1.en

(v) = 0,KÓœ¹1aqŒyw

(v) ≥0.e¡•Än

(v) = 1, Ø”d(v

) = 2.

bk=4,Kw(v)=2.dP1•, f

(v) +f

(v)≤2.däó3.1•,d(f

)≥4…

d(f

)≥4.Ïd, f

(v)≤1.ef

(v)=1,Kf

(v)+ f

(v)≤1.dGØ¹H

•†v'é3-¡

7•(4,5

)-¡.dR1∼R4, w

(v)≥2 −1 −

.ef

(v)=0,Kf

(v) +f

(v)≤2.

(v)+f

(v) = 2ž, Kf

½f

•4-¡½5-¡, Ø”•f

.däó3.2•,f

•(2,4,4

)-¡½

5-¡.dR2 ∼R3•τ(v→f

) ≤

.dR2 ∼R4,w

(v) ≥2−1−

−

.f

(v)+f

(v) ≤1

ž,dR2 ∼R4, w

(v) ≥2−1−

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

Çu$§‘û

bk= 5, Kw(v) = 4.dP1•,f

(v)+f

(v) ≤2.däó3.6•,vØ†(3

−

,5)-¡

'é.Ïd,dR1•v–õ‰'é3-¡=

.ldR1∼R4 •,w

(v)≥4 −1 −

(v)+

(v)+f

(v)) ≥4−1−

×2 = 0.

bk≥6,Kw(v)=2k−6.dP1 •, f

(v)+f

(v)≤b

c.däó3.6 •,vØ†

−

,k)-¡'é.dR1•v–õ‰'é3-¡=

.dR1 ∼R4,w

(v) ≥2k−6−1−

×b

c≥

2k−7−

k−7 >0.t

äó3.9éz‡f∈F(G) Ñkw

(f) ≥0.

y²bd(f) ≥6,Kw

(f) = w(f) ≥0.e¡•Ä3 ≤d(f) ≤5.e¡f†2-:'é,KÓœ

¹2aqŒy.e¡fØ†2-:'é,KÓœ¹1aqŒy.t

nþ?ØŒ•,ØAÏ2-:,é∀x∈V(G)∪F(G),kw

(x) ≥0.däó3.7•ã¥–õ•3

˜‡AÏ2-:.Ïd,−12 =

x∈V(G)∪F(G)

w(x) =

x∈V(G)∪F(G)

(x) ≥−2,gñ.Ïd,‡~Ø•3,

=Ún4¤á.

œ¹4δ(G) = 1.

duGØ¹fã/H

ÚH

,ÏdãGäkXe5Ÿ.

äó4.1G¥?Û3-¡Ñ´(3

−

)-¡½(4

)-¡.

äó4.2G¥†2-:'é4-¡•(2,5

)-¡.

du1-:ŒU¬'é˜‡š~5-¡,·‚^w

5L«1-:9Ù'éš~5-¡#Ú.

fœ/4.1G¥•31 ‡1-:,–õ2 ‡2-:.

dž‰1=£5KÓœ¹2.w,,Ø1-:9Ù'éš~5-¡±92-:,

·‚Œ±yéz‡x∈V(G)∪F(G),kw

(x)≥0.w

≥−4+(−1)=−5.Ïd,

−12 =

x∈V(G)∪F(G)

w(x) =

x∈V(G)∪F(G)

(x) ≥w

+2×(−2) = −9,gñ.Ïd,‡~Ø•3,=Ú

n4¤á.

fœ/4.2G¥•31 ‡1-:,–3 ‡2-:.

dž‰1=£5KÓœ¹3.w,,Ø1-:9Ù'éš~5-¡±9AÏ2-:

,·‚Œ±yéz‡x∈V(G) ∪F(G),kw

(x)≥0.w

≥−4+(−1)=−5.Ïd,

−12 =

x∈V(G)∪F(G)

w(x) =

x∈V(G)∪F(G)

(x) ≥w

+(−2) = −7,gñ.Ïd,‡~Ø•3,=Ún4

¤á.

fœ/4.3G¥•32 ‡1-:.

dGØ¹kfã/H

,KG¥Ø•3Ù¦2

−

-:,þ•3

-:.dž‰1=£5KÓ

œ¹1.w,,Ø1-:9Ù'éš~5-¡,·‚Œ±yéz‡x∈V(G) ∪F(G),k

(x)≥0.w

≥2 ×(−5)=−10.Ïd,−12=

x∈V(G)∪F(G)

w(x)=

x∈V(G)∪F(G)

(x)≥w

≥

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

Çu$§‘û

−10,gñ.Ïd,‡~Ø•3,=Ún4¤á.t

3.Ì‡½ny²

½n1eG´˜‡Ø¹ƒ5

−

-²¡ã,Ké?¿k≥max{∆,5},ãG´þ!k-Œ/

.

5‡:,KdÚn4 •,ãG–•¹H

∼H

˜‡fã/.e¡Ïékk‡º:f8S.

eG•¹fã/H

,i∈{2,4,7,10,12,13,14,16,17,18},-S

= {x

k−1

k−2

eG•¹fã/H

,i∈{3,5,6,9,15},-S

= {x

k−1

k−2

k−3

eG•¹fã/H

,i∈{1,8,11,19},-S

= {x

k−1

k−2

e¡lS

ÑuE8ÜS.dÚn2•G´3-òz,¤±G−S

•´3-òz.3

G−S

¥•Ý:,,3¤fã¥2•Ý:,···,ù-E:,·‚Œ±8Ü

S= {x

k−1

k−2

,···x

N´y,é∀x

∈S,1 ≤i≤kk|N

)−S|≤k−i.

-H=G−S⊆G,V(H)⊆V(G),K∆(H)≤∆.e∆(H)<∆,Kk≥max{∆,5}≥∆≥

∆(H)+1.KdÚn3 •,H´þ!k-Œ/.e∆(H)= ∆,KdG45•,H´þ!k-Œ

/.dÚn1 Œ•,G´þ!k-Œ/.t

íØ1z˜‡∆ ≥5 …Ø¹ƒ5

−

-²¡ã´þ!∆-Œ/.

½n2z˜‡Ø¹ƒ5

−

-²¡ã÷vßŽ3.

ë•©z

[1]Meyer,W.(1973)EquitableColoring.TheAmericanMathematicalMonthly,80,920-922.

https://doi.org/10.1080/00029890.1973.11993408

[2]Erd˝os,P.(1964)Problem9.In:Fielder,M.,Ed.,TheoryofGraphsandItsApplications,

PublishingHouseoftheCzechoslovakAcademyofSciences,Prague,159.

[3]Hajnal,A.andSzemer´edi,E.(1970)ProofofaConjectureofP.Erd˝os.In:Erd˝os,P.,R´enyi,

A. andS´os,V., Eds.,CombinatorialTheoryandItsApplications,North-Holland,Amsterdam,

601-623.

[4]Kierstead, H.A., Kostochka, A.V., Mydlarz, M. and Szemer´edi,E. (2010) A FastAlgorithm for

EquitableColoring.Combinatorica,30,217-224.https://doi.org/10.1007/s00493-010-2483-5

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

Çu$§‘û

[5]Chen,B.L.,Lih,K.W.andWu,P.L.(1994)EquitableColoringandtheMaximumDegree.

EuropeanJournalofCombinatorics,15,443-447.https://doi.org/10.1006/eujc.1994.1047

[6]Kierstead,H.A. andKostochka,A.V.(2012) Every 4-ColorableGraphwithMaximumDegree

4HasanEquitable4-Coloring.JournalofGraphTheory,71,31-48.

https://doi.org/10.1002/jgt.20630

[7]Chen,B.L.andLih,K.W.(1994)EquitableColoringofTrees.JournalofCombinatorialThe-

ory,SeriesB,61,83-87.https://doi.org/10.1006/jctb.1994.1032

[8]Lih,K.W.andWu,P.L.(1996)OnEquitableColoringofBipartiteGraphs.DiscreteMathe-

matics,151,155-160.https://doi.org/10.1016/0012-365X(94)00092-W

[9]Wang,W.F.andZhang,K.M.(2000)EquitableColoringsofLineGraphsandCompleter-

PartiteGraphs.JournalofSystemsScienceandComplexity,13,190-194.

[10]Kostochka,A.V.(2002)EquitableColoringsofOuterplanarGraph.DiscreteMathematics,

258,373-377.https://doi.org/10.1016/S0012-365X(02)00538-1

[11]Kostochka, A.V.andNakprasit,K. (2003) EquitableColoringsofk-Degenerate Graphs.Com-

binatorics, ProbabilityandComputing, 12, 53-60.https://doi.org/10.1017/S0963548302005485

[12]Yap,H.P.andZhang,Y.(1998)EquitableColoringsofPlanarGraphs.JournalofCombina-

torialMathematicsandCombinatorialComputing,27,97-105.

[13]Nakprasit,K.(2012)EquitableColoringsofPlanarGraphswithMaximumDegreeatLeast

Nine.DiscreteMathematics,312,1019-1024.https://doi.org/10.1016/j.disc.2011.11.004

[14]Zhu,J.L.and Bu,Y.H. (2008)Equitable ListColoringsofPlanar GraphswithoutShortCycles.

TheoreticalComputerScience,407,21-28.https://doi.org/10.1016/j.tcs.2008.04.018

[15]‘…,?Ó.Ø¹4-Ú5-²¡ãþ!/Ú[J].úô“‰ŒÆÆ(g,‰Æ‡),2014,

37(1):1-6.

[16]Zhu,J.L.,Bu,Y.H.andMin,X.(2015)EquitableList-ColoringforC

-FreePlaneGraphs

withoutAdjacentTriangles.GraphsandCombinatorics,31,795-804.

https://doi.org/10.1007/s00373-013-1396-7

[17]Dong,A.J.andWu,J.L.(2019)EquitableColoringandEquitableChoosabilityofPlanar

GraphswithoutChordal4-and 6-Cycles.DiscreteMathematicsTheoreticalComputerScience,

21,1-21.

[18]Sittitrai,P.andNakprasit,K.(2022)PlanarGraphswithoutMutuallyAdjacent3-,5-,and

6-CyclesAre3-Degenerate.DiscreteMathematics,345,ArticleID:112942.

https://doi.org/10.1016/j.disc.2022.112942

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