不含相邻短圈的平面图的 (3, 1)*-可选性 (3, 1)*-Choosability of Planar Graphs without Adjacent Short Cycles

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

期刊菜单

文章导航

AdvancesinAppliedMathematics A^êÆ?Ð,2019,8(9),1574-1586

PublishedOnlineSeptember2019inHans.//www.abtbus.com/journal/aam

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

(3 ,1)

∗

-ChoosabilityofPlanarGraphs

withoutAdjacentShortCycles

QianZhang

CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang

Received:Sep.1

,2019;accepted:Sep.16

,2019;published:Sep.23

,2019

Abstract

Foragraph G,alistassignmentisafunction Lthatassignsalist L(v)ofcolorstoeach

vertex v∈V(G).An (L,d)-coloringisamapping ϕthatassignsacolor ϕ(v)∈L(v)to

each v∈V(G)sothatatmost dneighborsof vreceivethecolor ϕ(v).Agraph Gissaid

tobe (k,d)

∗

-cho osableifitadmitsan (L,d)

∗

-coloringforeverylistassignment Lwith

| L(v)|≥ kforallv∈ V(G).XuandZhangconjecturedthateveryplanargraphwithout

adjacent 3-cyclesis (3,1)

∗

-cho osable.Inthispaper,weprovethateveryplanargraph

withoutadjacent k-cycles, k= 3,4,5,is (3,1)

∗

-cho osable.

Keywords

PlanarGraph,ImproperChoosability,Discharge,Cycle

Ø ¹ƒá²¡ã(3,1)

∗

- ŒÀ5

ÜÜÜ ÊÊÊ

ú ô“‰ŒÆ§êÆ†OŽÅ‰ÆÆ §ú ô7u

Â vFÏµ2019c91F¶¹^FÏµ2019c916F¶uÙFÏµ2019c923F

∗

- ŒÀ5[J]. A^êÆ?Ð,2019,8(9):1574-1586.

DOI:10.12677/aam.2019.89184

Ü Ê

Á ‡

ã G˜‡ôÚL˜L´•‰G¥z‡º:vÑ©˜‡Œ^Ú8L(v)"XJ3N

ϕ eé?¿v ∈V (G )þ÷vϕ (v )∈L (v )§¦3v :¥–õkd ‡º:ôÚ•ϕ (v )§@

o ·‚ ¡G´(L,d)

∗

- Œ/"XJé?¿ôÚL˜L={L(v)||L(v)|≥k,v∈V(G)},GÑ

´ (L,d)

∗

- Œ/§@o·‚Ò¡G´(k,d)

∗

- ŒÀ"XuÚZhangßŽ:Ø¹ƒ3-²

¡ ã´(3,1)

∗

- ŒÀ"3©¥§·‚òy²Ø¹ƒk-²¡ã´(3,1)

∗

- ŒÀ§Ù¥

k ∈{3, 4, 5}"

' …c

² ¡ã§š~L/Ú§=£§

 2019byauthor(s)andHansPublishersInc.

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

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

1. Úó

ã G˜‡ôÚL˜L´•‰G¥z‡º:vÑ©˜‡Œ^Ú8L(v)"XJ3N

ϕ eé?¿v ∈V (G )þ÷vϕ (v )∈L (v )§¦3v :¥–õkd ‡º:ôÚ•ϕ (v )§@

o ·‚ ¡G´(L,d)

∗

- Œ/"XJé?¿ÚLL={L(v)||L(v)|≥k,v∈V(G)}§ãGÑ´

( L,d)

∗

- Œ/§@o·‚Ò¡ãG´( k,d)

∗

- ŒÀ"

Skrekovski[1] †Eaton ÚHull[2] 31999 c

Ä gJÑš~/ÚVg§¿…y²¤k²¡ãÑ´ (3,2)

∗

- ŒÀ±9¤k²¡ã

Ñ ´(2,2)

∗

- ŒÀ"3©z[3]¥§Cowen<y²•3²¡ãØ´(3,1)

∗

- Œ/§¤±•Ò

` ²¿š¤ k²¡ãÑ´(3,1)

∗

- ŒÀ"@o3Ÿo^‡e²¡ã´(3,1)

∗

- ŒÀQº

Skrekovski[4] Äky²Ø¹3- ²¡ã´(3 ,1)

∗

- ŒÀ"‘§Lih<y²Ø¹4-

Ú k-²¡ã´(3,1)

∗

- ŒÀ§Ù¥k∈{5 ,6 ,7 }"d§DongÚXu[6]qy²Ø¹4-

Ú k-²¡ã´(3,1)

∗

- ŒÀ§Ù¥k∈{8 ,9 }"‘ §Wang[7]y²Ø¹4-²¡ã´

(3 ,1)

∗

- ŒÀ"3©z[8]¥§XuÚZhangJÑXeßŽµ

ß Ž1Ø¹ƒ3-²¡ã´(3,1)

∗

- ŒÀ"

3 ©¥§·‚y²ßŽ1¿©^‡Xeµ

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

Ü Ê

½ n1Ø¹ƒk-²¡ã´(3,1)

∗

- ŒÀ§Ù¥k∈{3 ,4 ,5 }.

 ©•Äãþ•Ã‚ÚÃ-> k•Ã•ã"e¡·‚é²¡ã¥˜Vg?1`²"

é u²¡ãG§^V(G)§E(G)§|V(G)|§|E(G)|Úδ(G)©OL«ãGº: 8§>8§º: ê§

> êÚ•Ý¶^d(v)Úd(f)©OL «º:vÝÚ¡fÝ"XJº:vÝuk(–´

k ½–õ´k )§K¡v ´k -:(k

- :½k

−

- :) "aq/½Âk-¡§k

−

- ¡Úk

- ¡"euv∈E(G)§

K ¡uv•(d(u),d(v))->"^b(f)L«f>.þ´"XJv

, ···,v

´ fþº:§KP•

f =[v

, ···,v

] ½( d( v

) ,d( v

) ,···,d( v

))- ¡"eu´v˜‡i-:¿…uvØ†3-¡ƒ'é§

K ¡u•vái-:"evk˜‡'é3-¡3-:…vØ3ù‡3-¡þ§K¡ù‡3-¡

´ v]!3-¡"XJ˜‡5-:'é˜‡(3,4,5)-¡Ú˜‡(4,5,5

)- ¡¿…k˜‡á3- 

: §@o·‚¡ù 5-: •€: §‡ƒ¡•Ð: "XJ˜‡6-:'éü‡(3,4,6)-¡Ú˜‡

(4 ,5

, 6)-¡§@·‚¡ù6-:•€:§‡ƒ¡•Ð:"éuk= 5,6§^k

- :( k

- :) 5L«

€ :(Ð:)"

2. ½n1 y²

b ½n1´Ø("G=(V,E)•½n1éu|V(G)|+ |E(G)|•4‡~§w,

ã G´ëÏ "·‚òl±eÚnÚ=£Ñgñ"

2.1. Œ5(

5 1-G•Ø¹ƒk-²¡ã x§Ù¥k∈{3,4,5}§KG∈G"ddŒ•ãG¥Ø¹

± eù(µ

(1) ƒ3- ¡¶

(2) ƒ4- ¡¶

(3) ƒ5- ¡¶

(4)3- ¡†ü‡4- ¡ƒ¶

(5)4- ¡†ü‡3- ¡ƒ¶

(6)5- ¡†ƒ3- ¡Ú4- ¡ƒ"

· ‚k0Wang3[7]¥‰ÑA‡Únµ

Ú n1[7]

(1) δ( G) ≥3;

(2) G¥Ø¹(3 ,3)- >"

Ú n2[7]

(1) G¥vk(4

−

, 4

−

, 4

−

)- ¡¶

(2) G¥vk(3 ,4 ,3 ,4)- ¡"

Ú n3[7]

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

Ü Ê

(1)4- :–õkü‡3- :¶

(2) e5- :†ü‡3- ¡ƒ'é§Ù¥k˜‡3- ¡´(3 ,4 ,5)- ¡§K,˜‡3- ¡Ø•(4

−

, 4

−

, 5)-

¡ ¶

(3) e5 †˜‡(3 ,4 ,5)- ¡f

ƒ 'é§KØb(f

) þ:§–õk˜‡3- :¶

(4) e6- :†3 ‡3- ¡ƒ'é§Ù¥k˜‡3- ¡´(3 ,4 ,6)- ¡§KÙ§ü‡3- ¡ØÓž•

−

, 4

−

, 6)-¡¶

(5) e5- :†ü‡(4 ,4 ,5)- ¡ƒ'é§K§vk3- :"

Ú n4G¥vk(4,5

, 5

)- ¡"

y µbf

=[ v

] •(4 ,5

, 5

)- ¡§éui=2 ,3, f

=[ x

] •(3 ,4 ,5)- ¡"v

- :§v

• v

 á3-: "éui=1,2§-x

• x

 á: §y

Ú y

• y

 á

: "dG45§ãG

= G−{v

} k˜‡(3,1)

∗

- /Úϕ( éz‡º:

x ∈V (G )5`§§/Ú5g uÚLL (x ))"Äk§•g‰v

˜ ‡~ /Ú",

 §‰v

/ L(v

) \{ϕ( v

) ,ϕ( y

) }¥ôÚ§‰v

/ L(v

) 3{ϕ( v

) ,ϕ( v

) ,ϕ( y

) ,ϕ( x

) }–

õ Ñy˜g ôÚ"•,‰x

/ L(x

) \{ϕ( v

) ,ϕ( x

) }¥ôÚ. dþŒ•Gk'uLL˜

‡ (3,1)

∗

- /Ú§gñ"

Ú n5G¥vk(4,5

, 6

)- ¡"

y µbf

=[ v

] •(4 ,5

, 6

)- ¡§f

=[ x

] •(3 ,4 ,5)- ¡"v

´ 5

- :§v

•

 á3-: §x

• x

 á: "éui= 3,4, -f

= [ x

] •(3 ,4 ,6)- ¡, x

• x

 

á :"dG45§ãG

= G−{v

} k'uLL˜‡(3,1)

∗

/Ú ϕ"Äk§•g‰v

 ~/Ú",§•g‰v

/ L(v

) \{ϕ( v

) ,ϕ( y

) }¥

ô Ú§x

/ L(x

) \{ϕ( x

) ,ϕ( v

) }¥ôÚ§v

/ L(v

) 3{ϕ( v

) ,ϕ( v

) ,ϕ( x

) ,ϕ( y

) }–õ

Ñ y˜gôÚ"•§‰x

/ L(x

) \{ϕ( v

) ,ϕ( x

) }¥ôÚ"dþŒ•Gk'uLL˜

‡ (3,1)

∗

- /Ú§gñ"

Ú n6G¥vk(4,6

, 6

)- ¡"

y µbf =[v

] •(4 ,6

, 6

)- ¡§éui=1 ,2, f

=[ x

] •(3 ,4 ,6)- ¡§é

u i=3,4,f

=[ x

] •(3 ,4 ,6)- ¡"-x

• x

 á: §Ù¥i=1,2,3,4"dG4

5 §ãG

= G−{v

} k'uLL(3,1)

∗

- /Úϕ"Äk§•

g ‰v

 ~/Ú",§•g‰v

/ L(v

) \{ϕ( y

) ,ϕ( y

) }¥ôÚ§‰x

L (x

) \{ϕ( v

) ,ϕ( x

) }¥ôÚ§Ù¥i=1 ,2 §‰v

/ L(v

) 3{ϕ( v

) ,ϕ( v

) ,ϕ( x

) ,ϕ( y

) }

– õÑy˜gôÚ"•§‰x

/ L(x

) \{ϕ( v

) ,ϕ( x

) }¥ôÚ"dþŒ•Gk'uLL

˜ ‡(3,1)

∗

- /Ú§gñ"

Ú n7e5-:'é˜‡(4

−

, 4, 5)-¡§K§Ø†(3, 4, 3, 5)-¡ƒ'é"

y µ5-:'é˜‡(3,4,5)-¡ž§dÚn3(3)Œ• (3,4,5)-¡†(3,4,3,5)-¡ƒ"b

 f

=[ v

,v ]•(3, 4, 5)-¡§f

=[ v

,u,v

,v ]•(3, 4, 3, 5)-¡"-vÙ§:•v

Ú v

• v

 á:"dG45§ãG

= G−{v,v

,u }k'uLL ˜‡(3, 1)

∗

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

Ü Ê

/Ú ϕ"Äk§•g‰v

,u ~/Ú",§•g‰v/L(v)\{ϕ(v

) ,ϕ( v

) }¥ôÚ§v

L (v

) \{ϕ( v

) ,ϕ( v) }¥ôÚ"•§‰v

/ L(v

) \{ϕ( u) ,ϕ( v) }¥ôÚ"dþŒ •G'uL

L ˜‡(3, 1)

∗

- /Ú§gñ"

 5-: 'é˜‡(4,4,5)-¡ž§dÚn1(2)Œ•(4,4,5)-¡Ø†(3,4,3,5)-¡ƒ"b

f =[v

,v ]•(4, 4, 5)-¡,f

=[ v

,u,v

,v ]•(3, 4, 3, 5)-¡.-v

• vÙ§:§v

• v

 Ù

§ :"dG45§ãG

= G−{v,v

,u }k'uLL ˜‡(3, 1)

∗

- /Úϕ"Ä

k §•g‰v

, v

, u, v

 ~/Ú",§•g‰v/L(v)\{ϕ(v

) }…3{ϕ( v

) ,ϕ( v

) }¥•

Ñ y˜gôÚ"•§‰v

/ L(v

) \{ϕ( v) ,ϕ( v

) }¥ôÚ"dþŒ•Gk'uLL˜‡

(3 ,1)

∗

- /Ú§gñ"

Ú n8e5-:'é˜‡(3,4,3,5)-¡f

§ KØb(f

) þ:§–õk˜‡3- :"

y µbf

=[ v

,u,v

,v ]•(3, 4, 3, 5)-¡"éui=3,4,5§-v

• vÙ§:§Ø”

Ú v

• 3-:§v

• v

 Ù§: .dG 45,ãG

= G−{v,v

,u }k'uL

L ˜‡(3, 1)

∗

- /Úϕ. Äk§•g‰u§v

, v

 ~/Ú",§•g‰v/L(v)\{ϕ(v

) }¿

… 3{ϕ(v

) ,ϕ( v

) }¥–õÑy˜gôÚ"•§‰v

/ L(v

) \{ϕ( v) ,ϕ( v

) }¥ôÚ"

d þŒ•Gk 'u LL˜‡(3,1)

∗

- /Ú§gñ"

Ú n9e6-:'éü‡(3,4,6)-¡f

Ú f

, KØb( f

) Úb( f

) þ:§vk3- :"

y µbf

= [ v

,v ]•(3, 4, 6)-¡§f

= [ v

,v ]•(3, 4, 6)-¡"-v

• v3-:§é

u i=2,4,5,v

Ú v

• v

 Ù§: §é ui=1,3,v

• v

 Ù§: "dG45§ã

= G−{v,v

} k'uLL˜‡(3,1)

∗

- /Úϕ"Äk§•g‰v

 ~

/Ú ",§•g‰v/L(v)\{ϕ(v

) }…3{ϕ( v

) ,ϕ( v

) }–õÑy˜gôÚ"•§‰

/ L(v

) \{ϕ( v) ,ϕ( v

) }¥ôÚ§v

/ L(v

) \{ϕ( v) ,ϕ( v

) }¥ôÚ"dþŒ•Gk'uL

L ˜‡(3, 1)

∗

- /Ú§gñ"

Ú n10e6-:'é˜‡(3,4,6)-¡f

Ú ˜‡(3,4,3,6)-¡f

, KØb( f

) Úb( f

) þ

: §–õ k˜‡3-: "

y ²µf

† f

ƒ ž§bf

=[ v

,v ]•(3, 4, 6)-¡§f

=[ v

,u,v

,v ]•(3, 4, 3, 6)-

¡ "éui=4,5,6§-v

• v:§Ø”v

Ú v

´ 3-:"éui=1,4,5§-v

Ú v

•

 Ù§: §v

• v

 Ù§: "dG45§ãG

= G−{v,v

,u,v

} k'u

L L˜‡(3,1)

∗

- /Úϕ"Äk§•g‰v

,u,v

 ~/Ú",§‰v/L(v)\ϕ(v

) }¿…

3 {ϕ(v

) ,ϕ( v

) }–õÑy˜gôÚ. •§‰v

/ L(v

) \{ϕ( v) ,ϕ( v

) }¥ôÚ§v

L (v

) \{ϕ( u) ,ϕ( v) }¥ôÚ"dþŒ•Gk'uLL˜‡(3,1)

∗

- /Ú§gñ"

 f

† f

Ø ƒž§bf

=[ v

,v ]´(3, 4, 6)-¡§f

=[ v

,u,v

,v ]•(3, 4, 3, 6)-¡"

é ui=5,6§-v

• vØ3b(f

) Úb( f

) þ3- :§v

• v

 Ù§: "dG4

5 §ãG

= G−{v,v

,u }k'uLL ˜‡(3, 1)

∗

- /Úϕ"Äk§•g‰

,u,v

 ~/Ú",§‰v/3{ϕ(v

) ,ϕ( v

) }–õÑy˜gô

Ú "•§ ‰v

/ L(v

) \{ϕ( v) ,ϕ( v

) }¥ôÚ"dþŒ•Gk 'uLL˜‡(3,1)

∗

- /Ú§

g ñ"

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

Ü Ê

2.2. =£5K

é ëÏ²¡ãG,dî.úª§k|V(G)|−|E(G)|+|F(G)|= 29

v ∈V (G )

d (v )=

f ∈F (G )

d (f )=

2 |E( G) |§Œµ

v ∈V (G )

(2 d( v) −6)+

f ∈F (G )

( d( f) −6)= −12

é z˜‡x∈V(G) ∪F(G)§½ ÂÙÐ©Š•ch(x)"é?¿v∈V(G)§½Âch(v)=

2 d( v) −6 §éuf∈F( G), ch( f) = d( f) −6 §K

x ∈V (G )∪F (G )

ch (x ) = −12 < 0.e¡½Â=£

5 K,-#©º:Ú ¡,¦éz‡x∈(V(G)∪F(G)),Ñkch

∗

( x) ≥0. du•3º:Ú

¡ ƒm?1=£§oÚØC§l0≤

x ∈V (G )∪F (G )

∗

( x)=

x ∈V (G )∪F (G )

ch (x )=−12< 0§

g ñ"`²4‡~Ø• 3§l½n¤á"·‚ò†€:ƒ'é¡¡•€¡§ÄK¡•Ð¡"

± eXJvkAO`²Ð¡†€¡Œw¤ü‡«œ¹e€:†Ð:=œ¹˜ "

 =£5KX eµ

R14- :=œ¹

R1 .1 ‰z‡]!3- ¡=

R1 .2 ‰z‡†§ƒ'é3- ¡=

R1 .3 ‰z‡†§ƒ'é4- ¡=œ¹¶

(1) ‰z‡†§ƒ'é(3 ,4 ,3

, 4

)- ¡=

(2) ‰z‡†§ƒ'é(4 ,4

, 4

)- ¡=

R1 .4 ‰ z‡†§ƒ'é5- ¡f=

5 −m

§ Ù¥m•b(f)þ3-:‡ê§ dÚn1(2)Œ

• m≤2"

R25

- :=œ¹

R2 .15

- :‰3- ¡=œ¹

(1) ‰z‡]!3- ¡=

(2) ‰z‡†§ƒ'é(3 ,4 ,5

)- ¡=2 ¶

(3) ‰z‡†§ƒ'é(4 ,4 ,5

)- ¡=

(4) ‰z‡†§ƒ'é(3 ,5

, 5

)- ¡=

(5) ‰z‡†§ƒ'éÐ(4 ,5

, 5

)- ¡=

§ €:‰z‡†§ƒ'é€(4,5

, 5

¡ =1§Ð:½7

- :=

(6) ‰z‡†§ƒ'é(5

, 5

)- ¡=1 ¶

R2 .25

- :‰4- ¡=œ¹

(1) ‰z‡†§ƒ'é(3 ,4 ,3 ,5

)- ¡=

(2) ‰z‡†§ƒ'é(3 ,5

, 3, 5

)- ¡=1 ¶

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

Ü Ê

(3) ‰z‡†§ƒ'é(3 ,4

, 4

, 5

)- ¡=

(4) ‰z‡†§ƒ'é(4

, 4

, 5

)- ¡=

R2 .35

- :‰z‡† §ƒ'é5- ¡f=

5 −m

§ Ù¥m•b(f)þ3-:‡ ê§ dÚn1(2)

Œ •m≤2"

e ¡y#ch

∗

( x) ≥0 §x∈V(G)∪F(G)"

ä ó1∀f∈F(G),ch

∗

( f) ≥0 "

Š âd(f)Š§·‚Œ±©•±e4«œ¹?1?Ø"

œ ¹1µd(f) = 3§Kch(f) = 3−6 = −3"dÚn1Œ•G¥vkƒ3-:§¤±3-¡–õ'

é ˜‡3-:"

e f†˜‡3-:ƒ'é§KdÚn2(1)Œ•G¥vk(3,4,4)-¡§¤±f´(3,4,5

)- ¡½

(3 ,5

, 5

)- ¡"dÚn1(2)Œ•fþ3-::(Ø3fþ:)•4

- :"f´(3,4,5

¡ ž§dR1.1§R2.1(1)§R1.2ÚR2.1(2)Œ•3-::‰f=

,4- :‰f=

§ 5

- :‰f=

2 §¤±ch

∗

( f) = ch( f)+

× 1+

× 1+2× 1 = 0"f´(3,5

, 5

)- ¡ž§dR1 .1 §R2 .1(1) Ú

R2 .1(4) Œ•3- ::‰f=

§ 5

- :‰f=

§ ¤±ch

∗

( f) = ch( f)+

× 1+

× 2 = 0"

e fØ†3-:ƒ'é§KdÚn2(1)Œ•G¥vk(4,4,4)-¡§¤±f´(4,4,5

)- ¡§

(4 ,5

, 5

)- ¡½(5

, 5

)- ¡"3-¡´(4,4,5

)- ¡ž§dR1 .2 ÚR2 .1 Œ•4- :‰f=

- :‰f=

§ ¤±ch

∗

( f) = ch( f)+

× 2+

× 1 = 0"3-¡´(5

, 5

)- ¡ž§dR2 .1 Œ

• 5

- :‰f=1 §¤±ch

∗

( f)= ch( f)+1 ×3 =0 "3-¡´(4,5

, 5

)- ¡ž§dÚn4 ,5 ,6 Œ

• fþ– õ˜‡€:"fþvk€:ž§dR1.2ÚR2.1(5)Œ•4-:‰f=

§ 5

- :‰f=

¤ ±ch

∗

( f)= ch( f) +

× 2+

× 2=0"fþk˜‡€:ž§dR1.2ÚR2.1(5)Œ•4-:‰

f =

§ Ð5

- :‰f=

§ €5

- :‰f=1 §¤±ch

∗

( f) = ch( f)+

× 2+

× 1+1× 1 = 0.

œ ¹2µd(f) = 4§ Kch(f) = 4−6= −2"dÚn1Œ •G¥vkƒ3-:§¤±4-¡–õ'

éü ‡3-:"

e f†ü‡3-:ƒ'é§KdÚn2(2)Œ•fØ•(3,4,3,4)-¡§¤±f´(3,4,3,5

)- ¡½

(3 ,5

, 3, 5

)- ¡"f´(3,4,3,5

)- ¡ž§dR1 .3(1) ÚR2 .2(1) Œ•4- :‰f=

§ 5

- :‰f=

§ ¤±ch

∗

( f) = ch( f)+

× 1+

× 1 = 0"f´(3,5

, 3, 5

)- ¡ž§dR2.2(2)Œ•z‡5

- :

‰ f=1§¤±ch

∗

( f) = ch( f)+1 ×2 = 0 "

e f†˜‡3-:ƒ'é§Kf´(3,4

, 4

)- ¡§dR1 .3(1) ÚR2 .2(1)(2) Œ•z‡4

- :‰

f –=

§ ¤±ch

∗

( f) ≥ch( f)+

× 3 = 0"

e fØ†3-:ƒ'é§Kf´(4

, 4

)- ¡§dR1 .3(2) ÚR2 .2(4) Œ•z‡4

- :‰f–

 =

§ ¤±ch

∗

( f) ≥ch( f)+

× 4 = 0"

œ ¹3µd(f)=5§Kch(f)=5−6=−1"dR1.4ÚR2.3Œ•z‡4

- :‰=

5 −m

§ ¤±

∗

( f) = ch( f)+

5 −m

× (5− m) = 0"

œ ¹4µd(f) ≥6§Kd=£5KŒ•fØu)=£§¤±ch

∗

( f) = ch( f) = d( f) −6 ≥0 "

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

Ü Ê

ä ó2∀v∈V(G)§ch

∗

( v) ≥0 "

- t•v'é 3-¡‡ê§q•v'é4-¡‡ê§s•v'é5-¡‡ê§p•v]

! 3-¡‡ê§Ù¥t,q,s,p∈N"±eJ3-¡Ú 4-¡Ñ´•†vƒ' é"dÚn1Œ•Š

â d(v)Š·‚Œ±©•±e5«œ¹? 1?Ø"

d 51(1)(2)(3)Œ•G¥vk ƒ3-¡§4-¡Ú5-¡§¤±

t ≤b

d (v )

c (1)

q ≤b

d (v )

c (2)

s ≤b

d (v )

c (3)

d 51(1)(5)Œ•G¥vk ƒ3-¡…4-¡Ø† ü‡3-¡ƒ§¤±

p ≤d (v )−2×t −q (4)

œ ¹1µd(v) = 3§Kd=£5KŒ•vØu)=£§¤±ch

∗

( v) = ch( v) = 2 ×3 −6 = 0.

œ ¹2µd(v) = 4§Kch(v) = 2×4−6 = 2"d(1)ªŒ•t≤2§

e t=2§Kd51(1)(5)Œ•G¥3-¡Ø†3-¡ƒ…4-¡Ø†ü‡3-¡ƒ§¤±

q = 0"d(2)ªÚ(4)ªŒ•s≤2,p= 0.dR1.2ÚR1.4Œ•v‰z‡'é3-¡=

, ‰z‡'

é 5-¡–õ=

§ ¤±ch

∗

( v) ≥ch( v) −

× 2−

× 2 = 0"

e t= 1§Kd51(2)(4)Œ•G¥4-¡Ø†4-¡ƒ…3-¡Ø†ü‡4-¡ƒ§¤±q≤1"

 q= 0ž§d(3)ªÚ(4)ªŒ•s≤2,p≤2"dR1.2§R1.4ÚR1.1Œ•v‰z‡'é3-¡=

§ ‰z‡'é5-¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 1−

× 2−

× 2 = 0"

 q= 1ž§e3-¡†4-¡ƒ§Kd51(6)Œ•5-¡Ø†ƒ 3-¡Ú4-¡ƒ§¤±s= 0"

d (4)ªŒ•p≤1"dR1.2§R1.3ÚR1.1Œ•v‰z‡'é 3-¡=

§ ‰z‡'é4-¡–õ

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 1−

× 1 =

" e3-¡Ø†4-¡ƒ§

d (3)ªŒ•s≤2§s= 0ž§d (4)ªŒ•p≤2"1 ≤s≤2ž§d51(1)(6)Œ•3-¡Ø†

3- ¡ƒ…5- ¡Ø†ƒ3- ¡Ú4- ¡ƒ§¤±p=0 "ddŒ•s+p≤2"dR1Œ•v‰

z ‡'é3-¡ =

§ ‰z‡'é4-¡–õ=

§ ‰z‡'é5-¡–õ=

§ ‰]!3-¡=

, ¤±ch

∗

( v) ≥ch( v) −

× 1−

× 2 = 0.

e t=0§Kd(2)ªÚ(3)ªŒ•q≤2Ús≤2"q≤1ž§dÚn3(1)Œ•v–õkü

‡ 3-:§¤±p≤2"dR1.3§R1.4ÚR1.1Œ•v‰z‡'é4-¡–õ=

§ ‰z‡'é

5- ¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 1−

× 2−

× 2=0"q=2ž§

b s= 0,Kd(4)ªŒ•p≤2.b 1 ≤s≤2§Kd51(6)Œ•5-¡Ø†ƒ3-¡Ú4-¡ƒ

 §džp=0"nþŒ•s+p≤2§dR1.3§R1.4ÚR1.1Œ•v‰z‡'é4-¡–õ=

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

Ü Ê

‰ z‡ 'é5-¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 2−

× 2 = 0.

œ ¹3µd(v) = 5§ch(v) = 2×5−6 = 4"d(1)ªŒ•t≤2"

e t=0§Kd(2)ªÚ(3)ªŒ•q≤2Ús≤2"q=2ž§b s=0ž§d(4)ªŒ•

p ≤3"bs=1ž§d51(2)(6)Œ•4-¡Ø†4-¡ƒ…5-¡Ø†ƒ3-¡Ú4-¡ƒ§

d žp≤2"bs=2ž§d51(2)(6)Œ•4-¡Ø†4-¡ƒ…5-¡Ø†ƒ 3-¡Ú4-¡

ƒ §džp≤1"nþŒ•s+p≤3"dR2.2,R2.3ÚR2.1(1)Œ•v‰z‡'é4-¡–õ=

§ ‰z‡'é5-¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 2−

× 3=

" 

q ≤1ž§d(4)ªŒ•p ≤5"dR2.2§R2.3ÚR2.1(1)Œ•v‰z‡'é4-¡–õ=

§ ‰z

‡ 'é5-¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 1−

× 2−

× 5 =

e t=1§Kd(2)ªŒ•q≤2"q=0ž§d(3)ªÚ(4)ªŒ•s≤2,p≤3"dR2.1§

R2 .3 ÚR2 .1(1) Œ•v‰z‡'é3- ¡–õ=2 § ‰z‡'é5- ¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

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

× 2 −

× 3=

. q=1 ž§d(3) ªÚ(4) ªŒ•s≤2,

p ≤2"e3-¡´(3,4,5)-¡§KdÚn7Œ•vØ†(3,4,3,5)-¡ƒ'é"b3-¡Ø†4-¡

ƒ §KdÚn1(2)ÚÚn3(3)Œ•vØ†(3,4

, 3, 5

)- ¡ƒ'é"dR2.1(2),R2.2,R2.3Ú

R2 .1(1) Œ•v‰z‡'é3- ¡=2 §‰z‡'é4- ¡–õ=

§ ‰z‡'é5-¡–õ

§ ‰]!3-¡=

§ ¤±ch

∗

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

× 1 −

× 2 −

× 2=0"b3-

¡ †4-¡ ƒ§Kd51(6)Œ•5-¡ Ø†ƒ3-¡ Ú4-¡ ƒ§¤±s≤1"dR2.1(2)§

R2 .2,R2 .3 ÚR2 .1(1) Œ•v‰z‡'é3- ¡=2 §‰z‡'é4- ¡–õ=1 §‰z‡'

é 5-¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

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

× 3=0"

e 3-¡´(4,4,5)-¡§KdÚn7Œ•vØ†(3,4,3,5)-¡ƒ'é"dR2.1(3)§R2.2,R2.3Ú

R2 .1(1) Œ•v‰z‡'é3- ¡=

§ ‰z‡'é4-¡–õ=1,‰z‡'é5-¡–õ

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 1 − 1 × 1 −

× 2 −

× 2=0"e3-¡

´ (3,5,5

)- ¡½(4 ,5 ,5

)- ¡§KdR2 .1(4)(5) §R2 .2 §R2 .3 ÚR2 .1(1) Œ•v‰z‡'é3-

¡ =2§‰z ‡'é4-¡ –õ=1§‰z ‡'é5-¡ –õ=

§ ‰]!3-¡=

§ ¤±

∗

( v) ≥ch( v) −

× 1 −

× 4=0"q=2ž§d51(3)Œ•3-¡†4-¡ƒ§¤±

d 51(6)Ú(4)ªŒs=0Úp≤1"e3-¡´(3,4,5)-¡§KdÚn7Œ•vØ†(3,4,3,5)-¡

ƒ 'é"dÚn1(2)ÚÚn3(3)Œ•v–õ'é˜‡(3,5,3,5

)- ¡"dR2.1§R2.2ÚR2.1(1)Œ

• v‰z‡'é3-¡=2§ ‰Ù¥ ˜‡4-¡– õ=1§‰ ,˜‡4-¡– õ=

§ ‰]!3-¡=

§ ¤±ch

∗

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

× 1−

× 1=0"e3-¡´(3,5,5

)- ¡§KdÚn

8 Œ•ev'é˜‡(3 ,4 ,3 ,5)- ¡@ovØ2'é(3 ,4

, 3, 5)-¡"v'é˜‡(3,4,3,5)-¡ž§d

R2 .1 §R2 .2 ÚR2 .1(1) Œ•v‰z‡'é3- ¡=

§ ‰'é(3,4,3,5)-¡=

§ ‰,˜‡4-¡

– õ=

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 1−

× 1 =

" vØ'é

(3 ,4 ,3 ,5)- ¡ž§dR2 .1(4),R2 .2 ÚR2 .1(1) Œ•v‰z‡'é3- ¡=

§ ‰z‡'é4-¡–

õ =1§‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 1− 1× 2−

× 1 =

" e3-¡´(4,4

, 5)-¡§

K d51(3)Œ•3-¡†˜‡4-¡ƒ§¤ ±v–õ'é ˜‡(3,4

, 3, 5)-¡"dR2.1(3)§R2.2Ú

R2 .1(1) Œ•v‰z‡'é3- ¡=

§ ‰'éÙ¥˜‡4-¡–õ=

§ ‰,˜‡4-¡–õ=

‰ ]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 1−

× 1 = 0"

e t=2§Kd51(2)(5)Œ•4-¡Ø†4-¡ƒ…4-¡Ø†ü‡3-¡ƒ§¤±q≤1"

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

Ü Ê

 q=0ž§d(3)ªÚ(4)ªŒ•s≤2,p≤1"bp=0,KdÚn3(2)Œ•v–õ†˜‡

(3 ,4 ,5)- ¡ƒ'é"ev†˜‡(3,4,5)-¡ƒ'é§KdÚn3(2)Œ•vØ2†(4

−

, 4

−

, 5)-¡ƒ'

é "dR2.1ÚR2.3Œ•v‰'é(3,4,5)-¡=2§‰,˜‡'é3-¡–õ=

§ ‰z‡

' é5-¡–õ=

, ¤±ch

∗

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

× 1 −

× 2=0"evØ†(3,4,5)-¡

ƒ 'é§dR2.1ÚR2.3Œ•v‰'é3-¡–õ=

§ ‰z‡'é5-¡–õ=

§ ¤±

∗

( v) ≥ch( v) −

× 2 −

× 2=0"bp=1,KdÚn3(2)Œ•v–õ†˜‡(3,4,5)-¡

ƒ 'é"ev†˜‡(3,4,5)-¡ƒ'é§KdÚn3(2)Ú51(1)Œ•vØ2†(4

−

, 4

−

, 5)-¡±9

(3 ,5 ,5

) ƒ'é§Ïdv'é,˜‡3- ¡•(4 ,5 ,5

)- ¡½(5 ,5

, 5

)- ¡"v'é,˜‡

3- ¡•(4 ,5 ,5

)- ¡ž§v•5

- :"dR2.1(2)(5)ÚR2.3Œ•v‰'é(3,4,5)-¡=2§‰

(4 ,5 ,5

)- ¡=1 §‰z‡'é5-¡–õ=

§ ¤±ch

∗

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

× 2−

× 1 = 0"

 v'é ,˜‡3-¡•(5,5

, 5

)- ¡ž§dR2.1(2)(5)§R2.3ÚR2.1(1)Œ•v‰'é(3,4,5)-

¡ =2§‰(5,5

, 5

)- ¡=1 §‰z‡'é5- ¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥

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

× 2−

× 1 = 0"evØ†(3,4,5)-¡ƒ 'é§v†ü‡(4,4,5)-¡ƒ

' éž§Kd51(1)Ú Ún3(5)Œ•p= 0"dR2.1(3)ÚR2.3Œ•v‰'é(3,4,5)-¡=2§‰

(5 ,5

, 5

)- ¡=1 §‰z‡'é5-¡–õ=

§ ¤±ch

∗

( v) ≥ch( v) −

× 2−

× 2 = 0"vØ†

ü ‡(4,4,5)-¡ƒ'é ž§dR2.1,R2.3ÚR2.1(1)Œ•v‰'é ˜‡3-¡–õ=

§ ‰,˜‡

' é3-¡–õ=

§ ‰(5,5

, 5

)- ¡=1, ‰z‡'é5- ¡–õ=

§ ‰]!3-¡=

§ ¤±

∗

( v) ≥ch( v) −

× 1−

× 2−

× 1 = 0"q= 1ž§d51(1)(6)Œ•s= 0,p= 0"d

Ú n3(2)Œ•v–õ'é˜ ‡(3,4,5)-¡"ev'é˜‡(3,4,5)-¡"KdÚn3(2)Œ•vØ2†

−

, 4

−

, 5)-¡ƒ'é"4-¡†(3,4,5)-¡ƒž§dÚn7Œ•4-¡Ø•(3,4,3,5)-¡"e4-¡

Ø ´(3,5,3,5

)- ¡§KdR2 .1(2)(3) ÚR2 .2(3) Œ•v‰'é(3 ,4 ,5)- ¡=2 §‰,˜‡3- ¡=

§ ‰z‡'é4-¡–õ=

§ ¤±ch

∗

≥ ch(v)− 2× 1−

× 1−

× 1 = 0"e4-¡´(3,5,3,5

¡ §dÚn3(3)Œ•v'éÙ§3-¡Ø´(3,5,5

)- ¡"Ù§3-¡´(4,5,5

)- ¡ž§v´5

- :§

d R2.1(2)(5)ÚR2.2(2)Œ•v‰'é(3,4,5)-¡=2,‰,˜‡(4,5,5

)- ¡=1 §‰z‡'é

(3 ,5 ,3 ,5

)- ¡=1 §¤±ch

∗

= ch( v) −2 ×1 −1 ×1 −1 ×1=0 ¶Ù§3- ¡ ´(5 ,5

, 5

)- ¡§

d R2.1(2)(6)ÚR2.2(2)Œ•v‰'é(3,4,5)-¡=2§‰,˜‡(5,5

, 5

)- ¡=1 §‰z‡'é

 (3,5,3,5

)- ¡=1 §¤±ch

∗

( v) = ch( v) −2 ×1 −1 ×1 −1 ×1 = 0 "4-¡Ø†(3,4,5)-¡ƒ

 §d Ún3(3)Œ•4-¡Ø•(3,4

, 3, 5)"dR2.1ÚR2.2Œ•v‰'é(3,4,5)-¡=2§‰,

˜ ‡3-¡–õ=

§ ‰z‡'é4-¡ –õ=

§ ¤±ch

∗

≥ ch(v)− 2× 1−

× 1−

× 1=0¶

e vØ†(3,4,5)-¡ƒ'é"v†(4,4,5)-¡ƒ'é§dÚn7Œ•4-¡Ø•(3,4,3,5)-¡"XJ

v 'éü‡(4, 4, 5)-¡§K4-¡Ø•(3, 4

, 3, 5)-¡"dR2.1ÚR2.2Œ•v‰'é(4,4,5)-¡=

§ ‰'é4-¡–õ=

§ ¤±ch

∗

≥ ch(v) −

× 2 −

× 1=0¶XJv'é ˜‡(4,4,5)-¡§

d R2.1ÚR2.2Œ•v‰'é(4,4,5)-¡ =

§ ‰,˜‡3-¡–õ=

§ ‰'é4-¡–õ=

1, ¤±ch

∗

≥ ch(v)−

× 1 −

× 1 − 1× 1=0.XJvØ'é(4,4,5)-¡§dR2.1ÚR2.2Œ•

v ‰'é3-¡–õ=

§ ‰'é4-¡–õ=

§ ¤±ch

∗

( v) ≥ch( v) −

× 2−

× 1 = 0.

œ ¹4µd(v) = 6§ch(v) = 2×6−6 = 6"d(1)ªŒ•t≤3"

e t=0§Kd(2)(4)ªŒ•q≤3,s≤6 −qÚp≤6 −q§dR2.2§R2.3ÚR2.1(1)Œ•

v ‰z‡'é4-¡–õ=

§ ‰z‡'é5-¡–õ=

, ‰]!3- ¡=

§ ¤±ch

∗

( v) ≥

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

Ü Ê

ch (v )−

× q−

× (6− q)−

× (6− q) ≥ 0"

e t=1§Kd51(2)(4)Œ•4-¡Ø†4-¡…3-¡Ø†ü‡4-¡ƒ§¤±q≤2"

q =2ž§d(4)ªŒ•p≤2"p=2ž§d51(1)(5)(6)Œ•4-¡Ø†4-¡ƒ§3-¡

Ø †ü‡4-¡ƒ…5-¡Ø †ƒ3-¡Ú4-¡ƒ§¤±s=0"p≤1ž§d(3)ªŒ

• s≤3"ddŒ•s+p≤4"dR2.1§R2.2§R2.3ÚR2.1(1)Œ•v‰z‡'é3-¡–

õ =2§‰z‡'é 4-¡–õ =

§ ‰z‡'é5-¡–õ=

§ ‰]!3-¡=

§ ¤±

∗

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

× 2−

× 4=0"q≤1ž§d(3)ªÚ(4)ªŒ•s≤3,p≤4"d

R 2. 1§R 2. 2§R 2. 3ÚR 2. 1(1)Œ•ch

∗

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

× 1−

× 3−

× 4 =

e t=2§Kd51(2)(4)Œ•4-¡Ø†4-¡ƒ…3-¡Ø†ü‡4-¡ƒ§¤±q≤2"

d (4)ªŒ•p≤2"dÚn6(4)Œ•v–õ'éü‡(3,4,6)-¡"v†ü‡(3,4,6)-¡ƒ'

é ž§dÚn 9Ú51(1)Œ•v†ü ‡(3,4,6)-¡ƒ'é ž§vvká 3-:…3-¡Ø†

3- ¡ƒ§¤±p=0 §s≤4 −q"dÚn9Œ•v†ü‡(3,4,6)-¡ƒ'éž§†v'é

 4-¡Ø•(3,4

, 3, 6)-¡"dR2.1(2)§R2.2ÚR2.3Œ•v‰z‡'é3-¡=2§‰'

é 4-¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

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

× q−

(4 −q) ≥0 "

 v'é˜‡(3,4,6)-ž§XJq=2§Kd51(1)(2)(6)Œ•s=0…d(4)ªŒ•p=0"d

Ú n10Œ•ü‡4-¡ØÓž•(3,4,3,6)-¡"dR2.1ÚR2.2Œ•v‰z‡'é(3,4,6)-¡

= 2§‰,˜‡3-¡–õ=

§ ‰Ù¥˜‡4-¡–õ=

§ ‰,˜‡4-¡–õ=1§ ¤±

∗

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

× 1 −

× 1 − 1 × 1=0¶XJq=1§Kd(4)ªŒ•p≤ 1"

p =1ž§d51(1)(5)(6)Œ•s ≤1"p=0ž§d(3)ªŒ•s≤3"ddŒs+ p≤3"d

R 2. 1§R 2. 2§R 2. 3ÚR 2. 1(1)Œ•v ‰z‡'é(3, 4, 6)-¡=2§‰,˜‡3-¡–õ=

§ ‰'

é 4-¡–õ=

§ ‰,˜‡4-¡–õ=1§ ‰'é5-¡–õ=

§ ‰]!3-¡=

§ ¤±

∗

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

× 1 −

× 3=0"vØ†(3,4,6)-¡ƒ'éž§XJq=2§

K d51(1)(2)(6)Œ•s= 0"d(4)ªŒ•p= 0"dR2.1ÚR2.2Œ•v‰z‡'é3-¡–õ

= 2§‰ 'é4-¡–õ=

§ ¤±ch

∗

( v) ≥ch( v) −

× 2−

× 2=0"XJq=1§Kd(4)ª

Œ •p≤1"p=1ž§d51(1)(5)(6)Œ•s≤1"p=0ž§d(3)ªŒ•s≤3"ddŒ

s +p ≤3"dR2.1§R2.2§R2.3ÚR2.1(1)Œ•v‰z‡'é3-¡–õ=

§ ‰'é4-¡–õ=

§ ‰'é5-¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 2−

× 1−

× 3 =

" XJ

q = 0§Kd(3)ªÚ(4)ªŒ•s ≤3,p ≤2"dR2.1§R2.3ÚR2.1(1)Œ•v‰z‡'é3-¡–õ

§ ‰'é5-¡–õ=

§ ‰]!3-¡=

§ ¤±ch

∗

( v) ≥ch( v) −

× 2−

× 3−

× 2 = 1"

e t= 3§Kd51(1)(4)Œ•q=0§d(3)ªÚ(4)ªŒ•s≤3,p=0"dÚn6(4)Œ•v–

õ †ü‡(3,4,6)-¡ƒ'é"v†ü‡(3,4,6)-¡ƒ'éž§d Ún6(4)ÚÚn9Œ •Ù§3-¡

´ (4,5

, 6

)- ¡½(5

, 5

, 6)-¡"dR2.1(2)(5)(6)ÚR2.3Œ•v‰z‡'é(3,4,6)-¡=2§‰

Ù §3-¡–õ=1§‰z‡'é5-¡–õ=

§ ¤±ch

∗

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

× 3 = 0"

 v†˜‡(3,4,6)-¡ƒ'éž§dÚn6(4)Œ•v–õ k˜‡(4,4,6)-¡§dR2.1ÚR2.3Œ

• v‰'é(3,4,6)-¡=2§‰Ù¦3-¡– õ=

§ ‰z‡'é5-¡–õ=

, ¤±

∗

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

× 1−

× 3 = 0.vØ†(3,4,5)-¡ƒ'é§dR2.1ÚR2.3Œ•

v ‰'é3-¡–õ=

§ ‰z‡'é5-¡–õ=

§ ¤±ch

∗

( v) ≥ch( v) −

× 3−

× 3 = 0"

œ ¹5µd(v) ≥7§ch(v) = 2d(v)−6"-k•†vƒ'é3-¡Ú4-¡ƒêþ"

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

Ü Ê

d 51(1)(2)(4)(5)Œ•

k ≤b

d (v )

c (5)

q ≤(k +b

d (v )−3k

c )− (t− k) = b

d (v )−3k

c +2k− t(6)

s ≤d (v )−(t +q )−k (7)

d (1)ª§(4)ª§(5)ª§(6)ªÚ(7)ªŒ

∗

( v) ≥2 d( v) −6 −(2 t+

q +

s +

p )

≥ d(v)− 6− [2t+

q −

( d( v) −( t+ q) −k)+

( d( v) −2 ×t−q)]

≥

d (v )−6−(t +

q −

k )

≥

d (v )−6−[t +

× (b

d (v )−3k

c +2k− t)−

k ]

≥ d(v)− 6−

e d(v)=2r+1§Ù¥r≥3§Kch

∗

( v) ≥

r −5≥0¶ed (v )=2r §Ù¥r ≥4§

K ch

∗

( v) ≥

r −6 > 0"

d þŒ•§é?¿x∈V∪F§ch

∗

( v) ≥0 ®y§¤±½n1 y"

ë •©z

[1]

Skrekovski,R.(1999)ListImproperColoringofPlanarGraphs. Combinatorics,Probability

andComputing ,8,293-299.https://doi.org/10.1017/S0963548399003752

[2]Eaton,N.andHull,T.(1999)DefectiveListColoringsofPlanarGraphs. Bulletinofthe

InstituteofCombinatoricsandItsApplications ,25,79-87.

[3]Cowen, L.J., Cowen, R.H.and Woodall, D.R. (1986)DefectiveColorings ofGraphs inSurfaces:

PartitionsintoSubgraphsofBoundedValency. JournalofGraphTheory,10,187-195.

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

[4]

Skrekovski, R.(1999) Gr¨ostzsch-Type Theoremfor ListColorings withImproprietyOne. Com-

binatorics,ProbabilityandComputing ,8,493-507.

https://doi.org/10.1017/S096354839900396X

[5]Lih,K.W.(2001)ANoteonListImproperColoringPlanarGraphs. AppliedMathematics

Letters ,14,269-273.https://doi.org/10.1016/S0893-9659(00)00147-6

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

Ü Ê

[6]Dong,W.andXu,B.(2009)ANoteonListImproperColoringofPlaneGraphs. Discrete

AppliedMathematics ,157,433-436.https://doi.org/10.1016/j.dam.2008.06.023

[7]Wang, Y.andXu,L. (2013) ImproperChoosabilityofPlanarGraphswithout4-Cycles. SIAM

JournalonDiscreteMathematics ,27,2029-2037.https://doi.org/10.1137/120885140

[8]Xu,B.andZhang,H.(2007)EveryToroidalGraphswithoutAdjacentTrianglesIs(4 ,1)

∗

Choosable. DiscreteAppliedMathematics,155,74-78.

https://doi.org/10.1016/j.dam.2006.04.042

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