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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematicsA^êÆ?Ð,2019,8(9),1574-1586
PublishedOnlineSeptember2019inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2019.89184
(3,1)
∗
-ChoosabilityofPlanarGraphs
withoutAdjacentShortCycles
QianZhang
CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang
Received:Sep.1
st
,2019;accepted:Sep.16
th
,2019;published:Sep.23
rd
,2019
Abstract
ForagraphG,alistassignmentisafunctionLthatassignsalistL(v)ofcolorstoeach
vertexv∈V(G).An(L,d)-coloringisamappingϕthatassignsacolorϕ(v)∈L(v)to
eachv∈V(G)sothatatmostdneighborsofvreceivethecolorϕ(v).AgraphGissaid
tobe(k,d)
∗
-cho osableifitadmitsan(L,d)
∗
-coloringforeverylistassignmentLwith
|L(v)|≥kforallv∈V(G).XuandZhangconjecturedthateveryplanargraphwithout
adjacent3-cyclesis(3,1)
∗
-cho osable.Inthispaper,weprovethateveryplanargraph
withoutadjacentk-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
©ÙÚ^:ÜÊ.عƒá²¡ã(3,1)
∗
-ŒÀ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/Ú§=£§
Copyright
c
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]31999c
Ä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.891841575A^êÆ?Ð
ÜÊ
½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
1
,v
2
,···,v
n
´fþº:§KP•
f=[v
1
v
2
,···,v
n
]½(d(v
1
),d(v
2
),···,d(v
n
))-¡"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
b
-:(k
g
-:)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(
51-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.891841576A^êÆ?Ð
ÜÊ
(1)4-:–õkü‡3-:¶
(2)e5-:†ü‡3-¡ƒ'é§Ù¥k˜‡3-¡´(3,4,5)-¡§K,˜‡3-¡Ø•(4
−
,4
−
,5)-
¡¶
(3)e5†˜‡(3,4,5)-¡f
1
ƒ'é§KØb(f
1
)þ:§–õk˜‡3-:¶
(4)e6-:†3‡3-¡ƒ'é§Ù¥k˜‡3-¡´(3,4,6)-¡§KÙ§ü‡3-¡ØÓž•
(4
−
,4
−
,6)-¡¶
(5)e5-:†ü‡(4,4,5)-¡ƒ'é§K§vk3-:"
Ún4G¥vk(4,5
b
,5
b
)-¡"
yµbf
1
=[v
1
,v
2
,v
3
]•(4,5
b
,5
b
)-¡§éui=2,3,f
i
=[x
i
,y
i
,v
i
]•(3,4,5)-¡"v
i
´
5
b
-:§v
0
i
•v
i
á3-:"éui=1,2§-x
0
i
•x
i
á:§y
0
i
Úy
00
i
•y
i
á
:"dG45§ãG
0
= G−{v
1
,v
2
,v
3
,v
0
2
,v
0
3
,x
2
,y
2
,x
3
,y
3
}k˜‡(3,1)
∗
-/Úϕ(éz‡º:
x∈V(G)5`§§/Ú5g uÚLL(x))"Äk§•g‰v
1
,v
0
2
,v
0
3
,y
2
,y
3
,x
3
˜‡~ /Ú",
§‰v
2
/L(v
2
)\{ϕ(v
0
2
),ϕ(y
2
)}¥ôÚ§‰v
3
/L(v
3
)3{ϕ(v
1
),ϕ(v
2
),ϕ(v
0
3
),ϕ(y
3
),ϕ(x
3
)}–
õÑy˜gôÚ"•,‰x
2
/L(x
2
)\{ϕ(v
2
),ϕ(x
0
2
)}¥ôÚ.dþŒ•Gk'uLL˜
‡(3,1)
∗
-/Ú§gñ"
Ún5G¥vk(4,5
b
,6
b
)-¡"
yµbf
1
=[v
1
,v
2
,v
3
]•(4,5
b
,6
b
)-¡§f
2
=[x
2
,y
2
,v
2
]•(3,4,5)-¡"v
2
´5
b
-:§v
0
2
•
v
2
á3-:§x
0
2
•x
2
á:"éui= 3,4, -f
i
= [x
i
,y
i
,v
3
] •(3,4,6)-¡,x
0
i
•x
i

á:"dG45§ãG
0
= G−{v
1
,v
2
,v
3
,v
0
2
,x
2
,y
2
,x
3
,y
3
,x
4
,y
4
}k'uLL˜‡(3,1)
∗
-
/Úϕ"Äk§•g‰v
1
,v
0
2
,y
2
,y
3
,y
4
,x
4
~/Ú",§•g‰v
2
/L(v
2
)\{ϕ(v
0
2
),ϕ(y
2
)}¥
ôÚ§x
2
/L(x
2
)\{ϕ(x
0
2
),ϕ(v
2
)}¥ôÚ§v
3
/L(v
3
)3{ϕ(v
1
),ϕ(v
2
),ϕ(x
4
),ϕ(y
3
),ϕ(y
4
)}–õ
Ñy˜gôÚ"•§‰x
3
/L(x
3
)\{ϕ(v
3
),ϕ(x
0
3
)}¥ôÚ"dþŒ•Gk'uLL˜
‡(3,1)
∗
-/Ú§gñ"
Ún6G¥vk(4,6
b
,6
b
)-¡"
yµbf =[v
1
,v
2
,v
3
]•(4,6
b
,6
b
)-¡§éui=1,2,f
i
=[x
i
,y
i
,v
2
]•(3,4,6)-¡§é
ui=3,4,f
i
=[x
i
,y
i
,v
3
]•(3,4,6)-¡"-x
0
i
•x
i
á:§Ù¥i=1,2,3,4"dG4
5§ãG
0
=G−{v
1
,v
2
,v
3
,x
1
,x
2
,x
3
,x
4
,y
1
,y
2
,y
3
,y
4
}k'uLL(3,1)
∗
-/Úϕ"Äk§•
g‰v
1
,y
1
,y
2
,y
3
,y
4
,x
3
~/Ú",§•g‰v
2
/L(v
2
)\{ϕ(y
1
),ϕ(y
2
)}¥ôÚ§‰x
i
/
L(x
i
)\{ϕ(v
2
),ϕ(x
0
i
)}¥ôÚ§Ù¥i=1,2§‰v
3
/L(v
3
)3{ϕ(v
1
),ϕ(v
2
),ϕ(x
3
),ϕ(y
3
),ϕ(y
4
)}
–õÑy˜gôÚ"•§‰x
4
/L(x
4
)\{ϕ(v
3
),ϕ(x
0
4
)}¥ôÚ"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
1
=[v
2
,v
1
,v]•(3,4,5)-¡§f
2
=[v
2
,u,v
3
,v]•(3,4,3,5)-¡"-vÙ§:•v
4
Úv
5
,
v
0
3
•v
3
á:"dG45§ãG
0
=G−{v,v
1
,v
2
,v
3
,u}k'uLL˜‡(3,1)
∗
-
DOI:10.12677/aam.2019.891841577A^êÆ?Ð
ÜÊ
/Úϕ"Äk§•g‰v
1
,u~/Ú",§•g‰v/L(v)\{ϕ(v
4
),ϕ(v
5
)}¥ôÚ§v
3
/
L(v
3
)\{ϕ(v
0
3
),ϕ(v)}¥ôÚ"•§‰v
2
/L(v
2
)\{ϕ(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
1
,v
2
,v]•(4,4,5)-¡,f
2
=[v
3
,u,v
4
,v]•(3,4,3,5)-¡.-v
5
•vÙ§:§v
0
4
•v
4
Ù
§:"dG45§ãG
0
=G−{v,v
1
,v
2
,v
3
,v
4
,u}k'uLL˜‡(3,1)
∗
-/Úϕ"Ä
k§•g‰v
1
,v
2
,u,v
3
~/Ú",§•g‰v/L(v)\{ϕ(v
5
)}…3{ϕ(v
1
),ϕ(v
2
),ϕ(v
3
)}¥•
Ñy˜gôÚ"•§‰v
4
/L(v
4
)\{ϕ(v),ϕ(v
0
4
)}¥ôÚ"dþŒ•Gk'uLL˜‡
(3,1)
∗
-/Ú§gñ"
Ún8e5-:'阇(3,4,3,5)-¡f
1
§KØb(f
1
)þ:§–õk˜‡3-:"
yµbf
1
=[v
1
,u,v
2
,v]•(3,4,3,5)-¡"éui=3,4,5§-v
i
•vÙ§:§Ø”
v
3
Úv
4
•3-:§v
0
2
•v
2
Ù§:.dG45,ãG
0
=G−{v,v
1
,v
2
,v
3
,v
4
,u}k'uL
L˜‡(3,1)
∗
-/Úϕ.Äk§•g‰u§v
1
,v
3
,v
4
~/Ú",§•g‰v/L(v)\{ϕ(v
5
)}¿
…3{ϕ(v
1
),ϕ(v
3
),ϕ(v
4
)}¥–õÑy˜gôÚ"•§‰v
2
/L(v
2
)\{ϕ(v),ϕ(v
0
2
)}¥ôÚ"
dþŒ•Gk'uLL˜‡(3,1)
∗
-/Ú§gñ"
Ún9e6-:'éü‡(3,4,6)-¡f
1
Úf
2
,KØb(f
1
)Úb(f
2
)þ:§vk3-:"
yµbf
1
= [v
1
,v
2
,v]•(3,4,6)-¡§f
2
= [v
3
,x
4
,v]•(3,4,6)-¡"-v
5
•v3-:§é
ui=2,4,5,v
0
i
Úv
00
i
•v
i
Ù§:§éui=1,3,v
0
i
•v
i
Ù§:"dG45§ã
G
0
=G−{v,v
1
,v
2
,v
3
,v
4
,v
5
}k'uLL˜‡(3,1)
∗
-/Úϕ"Äk§•g‰v
2
,v
4
,v
5
~
/Ú",§•g‰v/L(v)\{ϕ(v
6
)}…3{ϕ(v
2
),ϕ(v
4
),ϕ(v
5
)}–õÑy˜gôÚ"•§‰
v
1
/L(v
1
)\{ϕ(v),ϕ(v
0
1
)}¥ôÚ§v
3
/L(v
3
)\{ϕ(v),ϕ(v
0
3
)}¥ôÚ"dþŒ•Gk'uL
L˜‡(3,1)
∗
-/Ú§gñ"
Ún10e6-:'阇(3,4,6)-¡f
1
Ú˜‡(3,4,3,6)-¡f
2
,KØb(f
1
)Úb(f
2
)þ
:§–õk˜‡3-:"
y²µf
1
†f
2
ƒž§bf
1
=[v
1
,v
2
,v]•(3,4,6)-¡§f
2
=[v
2
,u,v
3
,v]•(3,4,3,6)-
¡"éui=4,5,6§-v
i
•v:§Ø”v
4
Úv
5
´3-:"éui=1,4,5§-v
0
i
Úv
00
i
•
v
i
Ù§:§v
0
3
•v
3
Ù§:"dG45§ãG
0
=G−{v,v
1
,u,v
2
,v
3
,v
4
,v
5
}k'u
LL˜‡(3,1)
∗
-/Úϕ"Äk§•g‰v
1
,u,v
4
,v
5
~/Ú",§‰v/L(v)\ϕ(v
6
)}¿…
3{ϕ(v
1
),ϕ(v
4
),ϕ(v
5
)}–õÑy˜gôÚ.•§‰v
3
/L(v
3
)\{ϕ(v),ϕ(v
0
3
)}¥ôÚ§v
2
/
L(v
2
)\{ϕ(u),ϕ(v)}¥ôÚ"dþŒ•Gk'uLL˜‡(3,1)
∗
-/Ú§gñ"
f
1
†f
2
؃ž§bf
1
=[v
2
,v
1
,v]´(3,4,6)-¡§f
2
=[v
3
,u,v
4
,v]•(3,4,3,6)-¡"
éui=5,6§-v
i
•vØ3b(f
1
)Úb(f
2
)þ3-:§v
0
3
•v
3
Ù§:"dG4
5§ãG
0
=G−{v,v
1
,v
2
,v
3
,v
4
,v
5
,v
6
,u}k'uLL˜‡(3,1)
∗
-/Úϕ"Äk§•g‰
v
1
,v
2
,u,v
4
,v
5
,v
6
~/Ú",§‰v/3{ϕ(v
1
),ϕ(v
2
),ϕ(v
4
),ϕ(v
5
),ϕ(v
6
)}–õÑy˜gô
Ú"•§ ‰v
3
/L(v
3
)\{ϕ(v),ϕ(v
0
3
)}¥ôÚ"dþŒ•Gk 'uLL˜‡(3,1)
∗
-/Ú§
gñ"
DOI:10.12677/aam.2019.891841578A^êÆ?Ð
ÜÊ
2.2.=£5K
éëϲ¡ãG,dî.úª§k|V(G)|−|E(G)|+|F(G)|= 29
P
v ∈V(G)
d(v)=
P
f∈F(G)
d(f)=
2|E(G)|§Œµ
P
v ∈V(G)
(2d(v)−6)+
P
f∈F(G)
(d(f)−6)=−12
éz˜‡x∈V(G) ∪F(G)§½ÂÙЩŠ•ch(x)"é?¿v∈V(G)§½Âch(v)=
2d(v)−6§éuf∈F(G),ch(f) = d(f)−6§K
P
x∈V(G)∪F(G)
ch(x) = −12 <0.e¡½Â=£
5K,-#©º:Ú¡,¦éz‡x∈(V(G)∪F(G)),Ñkch
∗
(x)≥0.du•3º:Ú
¡ƒm?1=£§oÚØC§l0≤
P
x∈V(G)∪F(G)
ch
∗
(x)=
P
x∈V(G)∪F(G)
ch(x)=−12<0§
gñ"`²4‡~Ø• 3§l½n¤á"·‚ò†€:ƒ'é¡¡•€¡§ÄK¡•Ð¡"
±eXJvkAO`²Ð¡†€¡Œw¤ü‡«œ¹e€:†Ð:=œ¹˜"
=£5KXeµ
R14-:=œ¹
R1.1‰z‡]!3-¡=
1
3
¶
R1.2‰z‡†§ƒ'é3-¡=
2
3
¶
R1.3‰z‡†§ƒ'é4-¡=œ¹¶
(1)‰z‡†§ƒ'é(3,4,3
+
,4
+
)-¡=
2
3
¶
(2)‰z‡†§ƒ'é(4,4
+
,4
+
,4
+
)-¡=
1
2
¶
R1.4‰ z‡†§ƒ'é5-¡f=
1
5−m
§Ù¥m•b(f)þ3-:‡ê§dÚn1(2)Œ
•m≤2"
R25
+
-:=œ¹
R2.15
+
-:‰3-¡=œ¹
(1)‰z‡]!3-¡=
1
3
¶
(2)‰z‡†§ƒ'é(3,4,5
+
)-¡=2¶
(3)‰z‡†§ƒ'é(4,4,5
+
)-¡=
5
3
¶
(4)‰z‡†§ƒ'é(3,5
+
,5
+
)-¡=
4
3
¶
(5)‰z‡†§ƒ'éÐ(4,5
+
,5
+
)-¡=
7
6
§€:‰z‡†§ƒ'é€(4,5
+
,5
+
)-
¡=1§Ð:½7
+
-:=
4
3
¶
(6)‰z‡†§ƒ'é(5
+
,5
+
,5
+
)-¡=1¶
R2.25
+
-:‰4-¡=œ¹
(1)‰z‡†§ƒ'é(3,4,3,5
+
)-¡=
4
3
¶
(2)‰z‡†§ƒ'é(3,5
+
,3,5
+
)-¡=1¶
DOI:10.12677/aam.2019.891841579A^êÆ?Ð
ÜÊ
(3)‰z‡†§ƒ'é(3,4
+
,4
+
,5
+
)-¡=
2
3
¶
(4)‰z‡†§ƒ'é(4
+
,4
+
,4
+
,5
+
)-¡=
1
2
¶
R2.35
+
-:‰z‡† §ƒ'é5-¡f=
1
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-:"
ef†˜‡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=
1
3
,4-:‰f=
2
3
§5
+
-:‰f=
2§¤±ch
∗
(f) = ch(f)+
1
3
×1+
2
3
×1+2×1 = 0"f´(3,5
+
,5
+
)-¡ž§dR1.1§R2.1(1)Ú
R2.1(4)Œ•3-::‰f=
1
3
§5
+
-:‰f=
4
3
§¤±ch
∗
(f) = ch(f)+
1
3
×1+
4
3
×2 = 0"
ef؆3-:ƒ'é§KdÚn2(1)Œ•G¥vk(4,4,4)-¡§¤±f´(4,4,5
+
)-¡§
(4,5
+
,5
+
)-¡½(5
+
,5
+
,5
+
)-¡"3-¡´(4,4,5
+
)-¡ž§dR1.2ÚR2.1Œ•4-:‰f=
2
3
§
5
+
-:‰f=
5
3
§¤±ch
∗
(f) = ch(f)+
2
3
×2+
5
3
×1 = 0"3-¡´(5
+
,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=
2
3
§5
+
-:‰f=
7
6
§
¤±ch
∗
(f)=ch(f) +
2
3
×2+
7
6
×2=0"fþk˜‡€:ž§dR1.2ÚR2.1(5)Œ•4-:‰
f=
2
3
§Ð5
+
-:‰f=
4
3
§€5
+
-:‰f=1§¤±ch
∗
(f) = ch(f)+
2
3
×2+
4
3
×1+1×1 = 0.
œ¹2µd(f) = 4§ Kch(f) = 4−6= −2"dÚn1Œ •G¥vkƒ3-:§¤±4-¡–õ'
éü‡3-:"
ef†ü‡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=
2
3
§5
+
-:‰f=
4
3
§¤±ch
∗
(f) = ch(f)+
2
3
×1+
4
3
×1 = 0"f´(3,5
+
,3,5
+
)-¡ž§dR2.2(2)Œ•z‡5
+
-:
‰f=1§¤±ch
∗
(f) = ch(f)+1×2 = 0"
ef†˜‡3-:ƒ'é§Kf´(3,4
+
,4
+
,4
+
)-¡§dR1.3(1)ÚR2.2(1)(2)Œ•z‡4
+
-:‰
f–=
2
3
§¤±ch
∗
(f) ≥ch(f)+
2
3
×3 = 0"
ef؆3-:ƒ'é§Kf´(4
+
,4
+
,4
+
,4
+
)-¡§dR1.3(2)ÚR2.2(4)Œ•z‡4
+
-:‰f–
=
1
2
§¤±ch
∗
(f) ≥ch(f)+
1
2
×4 = 0"
œ¹3µd(f)=5§Kch(f)=5−6=−1"dR1.4ÚR2.3Œ•z‡4
+
-:‰=
1
5−m
§¤±
ch
∗
(f) = ch(f)+
1
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.891841580A^êÆ?Ð
ÜÊ
äó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?Ø"
d51(1)(2)(3)Œ•G¥vkƒ3-¡§4-¡Ú5-¡§¤±
t≤b
d(v)
2
c(1)
q≤b
d(v)
2
c(2)
s≤b
d(v)
2
c(3)
d51(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§
et=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-¡=
2
3
,‰z‡'
é5-¡–õ=
1
3
§¤±ch
∗
(v) ≥ch(v)−
2
3
×2−
1
3
×2 = 0"
et= 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-¡=
2
3
§‰z‡'é5-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v) ≥ch(v)−
2
3
×1−
1
3
×2−
1
3
×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-¡=
2
3
§‰z‡'é4-¡–õ
=
2
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v) ≥ch(v)−
2
3
×1−
2
3
×1−
1
3
×1 =
1
3
"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-¡=
2
3
§‰z‡'é4-¡–õ=
2
3
§‰z‡'é5-¡–õ=
1
3
§‰]!3-¡=
1
3
,¤±ch
∗
(v) ≥ch(v)−
2
3
×1−
2
3
×1−
1
3
×2 = 0.
et=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-¡–õ=
2
3
§‰z‡'é
5-¡–õ=
1
3
§ ‰]!3-¡=
1
3
§ ¤±ch
∗
(v)≥ch(v)−
2
3
×1−
1
3
×2−
1
3
×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-¡–õ=
2
3
§
DOI:10.12677/aam.2019.891841581A^êÆ?Ð
ÜÊ
‰z‡'é5-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v) ≥ch(v)−
2
3
×2−
1
3
×2 = 0.
œ¹3µd(v) = 5§ch(v) = 2×5−6 = 4"d(1)ªŒ•t≤2"
et=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-¡–õ=
4
3
§‰z‡'é5-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v)≥ch(v)−
4
3
×2−
1
3
×3=
1
3
"
q≤1ž§d(4)ªŒ•p≤5"dR2.2§R2.3ÚR2.1(1)Œ•v‰z‡'é4-¡–õ=
4
3
§‰z
‡'é5-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v) ≥ch(v)−
4
3
×1−
1
3
×2−
1
3
×5 =
1
3
"
et=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-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v)≥ch(v) −2 ×1 −
1
3
×2 −
1
3
×3=
1
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-¡–õ=
2
3
§‰z‡'é5-¡–õ
=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v)≥ch(v) −2 ×1 −
2
3
×1 −
1
3
×2 −
1
3
×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-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v)≥ch(v)−2×1−1×1−
1
3
×3=0"
e3-¡´(4,4,5)-¡§KdÚn7Œ•v؆(3,4,3,5)-¡ƒ'é"dR2.1(3)§R2.2,R2.3Ú
R2.1(1)Œ•v‰z‡'é3-¡=
5
3
§‰z‡'é4-¡–õ=1,‰z‡'é5-¡–õ
=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v)≥ch(v) −
5
3
×1 −1 ×1 −
1
3
×2 −
1
3
×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-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±
ch
∗
(v)≥ch(v)−
4
3
×1 −
4
3
×1 −
1
3
×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-¡–õ=
2
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v)≥ch(v) −2 ×1 −1 ×1 −
2
3
×1−
1
3
×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-¡=
4
3
§‰'é(3,4,3,5)-¡=
4
3
§‰,˜‡4-¡
–õ=
2
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v) ≥ch(v)−
4
3
×1−
4
3
×1−
2
3
×1−
1
3
×1 =
1
3
"vØ'é
(3,4,3,5)-¡ž§dR2.1(4),R2.2ÚR2.1(1)Œ•v‰z‡'é3-¡=
4
3
§‰z‡'é4-¡–
õ=1§‰]!3-¡=
1
3
§¤±ch
∗
(v) ≥ch(v)−
4
3
×1−1×2−
1
3
×1 =
1
3
"e3-¡´(4,4
+
,5)-¡§
Kd51(3)Œ•3-¡†˜‡4-¡ƒ§¤ ±v–õ'é ˜‡(3,4
+
,3,5)-¡"dR2.1(3)§R2.2Ú
R2.1(1)Œ•v‰z‡'é3-¡=
5
3
§‰'éÙ¥˜‡4-¡–õ=
4
3
§‰,˜‡4-¡–õ=
2
3
§
‰]!3-¡=
1
3
§¤±ch
∗
(v) ≥ch(v)−
5
3
×1−
4
3
×1−
2
3
×1−
1
3
×1 = 0"
et=2§Kd51(2)(5)Œ•4-¡Ø†4-¡ƒ…4-¡Ø†ü‡3-¡ƒ§¤±q≤1"
DOI:10.12677/aam.2019.891841582A^êÆ?Ð
ÜÊ
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-¡–õ=
4
3
§‰z‡
'é5-¡–õ=
1
3
,¤±ch
∗
(v)≥ch(v) −2 ×1 −
4
3
×1 −
1
3
×2=0"ev؆(3,4,5)-¡
ƒ'é§dR2.1ÚR2.3Œ•v‰'é3-¡–õ=
5
3
§‰z‡'é5-¡–õ=
1
3
§¤±
ch
∗
(v)≥ch(v) −
5
3
×2 −
1
3
×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
b
-:"dR2.1(2)(5)ÚR2.3Œ•v‰'é(3,4,5)-¡=2§‰
(4,5,5
+
)-¡=1§‰z‡'é5-¡–õ=
1
3
§¤±ch
∗
(v) ≥ch(v)−2×1−1×1−
1
3
×2−
1
3
×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-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v)≥
ch(v)−2×1−1×1−
1
3
×2−
1
3
×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-¡–õ=
1
3
§¤±ch
∗
(v) ≥ch(v)−
5
3
×2−
1
3
×2 = 0"v؆
ü‡(4,4,5)-¡ƒ'鞧dR2.1,R2.3ÚR2.1(1)Œ•v‰'é˜‡3-¡–õ=
5
3
§‰,˜‡
'é3-¡–õ=
4
3
§‰(5,5
+
,5
+
)-¡=1,‰z‡'é5-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±
ch
∗
(v) ≥ch(v)−
5
3
×1−
4
3
×1−
1
3
×2−
1
3
×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
−
,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-¡=
4
3
§‰z‡'é4-¡–õ=
2
3
§¤±ch
∗
≥ch(v)−2×1−
4
3
×1−
2
3
×1 = 0"e4-¡´(3,5,3,5
+
)-
¡§dÚn3(3)Œ•v'éÙ§3-¡Ø´(3,5,5
+
)-¡"Ù§3-¡´(4,5,5
+
)-¡ž§v´5
b
-:§
dR2.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
+
)-¡§
dR2.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-¡–õ=
4
3
§‰z‡'é4-¡ –õ=
2
3
§¤±ch
∗
≥ch(v)−2×1−
2
3
×1−
4
3
×1=0¶
ev؆(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)-¡=
5
3
§‰'é4-¡–õ=
2
3
§¤±ch
∗
≥ch(v) −
5
3
×2 −
2
3
×1=0¶XJv'é ˜‡(4,4,5)-¡§
dR2.1ÚR2.2Œ•v‰'é(4,4,5)-¡ =
5
3
§‰,˜‡3-¡–õ=
4
3
§‰'é4-¡–õ=
1,¤±ch
∗
≥ch(v)−
5
3
×1 −
4
3
×1 −1×1=0.XJvØ'é(4,4,5)-¡§dR2.1ÚR2.2Œ•
v‰'é3-¡–õ=
4
3
§‰'é4-¡–õ=
4
3
§¤±ch
∗
(v) ≥ch(v)−
4
3
×2−
4
3
×1 = 0.
œ¹4µd(v) = 6§ch(v) = 2×6−6 = 6"d(1)ªŒ•t≤3"
et=0§Kd(2)(4)ªŒ•q≤3,s≤6 −qÚp≤6 −q§dR2.2§R2.3ÚR2.1(1)Œ•
v‰z‡'é4-¡–õ=
4
3
§‰z‡'é5-¡–õ=
1
3
,‰]!3-¡=
1
3
§¤±ch
∗
(v)≥
DOI:10.12677/aam.2019.891841583A^êÆ?Ð
ÜÊ
ch(v)−
4
3
×q−
1
3
×(6−q)−
1
3
×(6−q) ≥0"
et=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-¡–õ=
4
3
§‰z‡'é5-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±
ch
∗
(v)≥ch(v) −2 ×1 −
4
3
×2−
1
3
×4=0"q≤1ž§d(3)ªÚ(4)ªŒ•s≤3,p≤4"d
R2.1§R2.2§R2.3ÚR2.1(1)Œ•ch
∗
(v) ≥ch(v)−2×1−
4
3
×1−
1
3
×3−
1
3
×4 =
1
3
"
et=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Ún9Ú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-¡–õ=
2
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v)≥ch(v) −2 ×2 −
2
3
×q−
1
3
(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-¡–õ=
5
3
§‰Ù¥˜‡4-¡–õ=
4
3
§‰,˜‡4-¡–õ=1§¤±
ch
∗
(v)≥ch(v) −2 ×1 −
5
3
×1 −
4
3
×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
R2.1§R2.2§R2.3ÚR2.1(1)Œ•v‰z‡'é(3,4,6)-¡=2§‰,˜‡3-¡–õ=
5
3
§‰'
é4-¡–õ=
4
3
§‰,˜‡4-¡–õ=1§‰'é5-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±
ch
∗
(v)≥ch(v) −2×1−
5
3
×1 −
4
3
×1 −
1
3
×3=0"v؆(3,4,6)-¡ƒ'鞧XJq=2§
Kd51(1)(2)(6)Œ•s= 0"d(4)ªŒ•p= 0"dR2.1ÚR2.2Œ•v‰z‡'é3-¡–õ
=2§‰ 'é4-¡–õ=
4
3
§¤±ch
∗
(v)≥ch(v)−
5
3
×2−
4
3
×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-¡–õ=
5
3
§‰'é4-¡–õ=
4
3
§‰'é5-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v) ≥ch(v)−
5
3
×2−
4
3
×1−
1
3
×3 =
1
3
"XJ
q= 0§Kd(3)ªÚ(4)ªŒ•s≤3,p≤2"dR2.1§R2.3ÚR2.1(1)Œ•v‰z‡'é3-¡–õ
=
5
3
§‰'é5-¡–õ=
1
3
§‰]!3-¡=
1
3
§¤±ch
∗
(v) ≥ch(v)−
5
3
×2−
1
3
×3−
1
3
×2 = 1"
et= 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
b
)-¡½(5
+
,5
+
,6)-¡"dR2.1(2)(5)(6)ÚR2.3Œ•v‰z‡'é(3,4,6)-¡=2§‰
Ù§3-¡–õ=1§‰z‡'é5-¡–õ=
1
3
§¤±ch
∗
(v) ≥ch(v)−2×2−1×1−
1
3
×3 = 0"
v†˜‡(3,4,6)-¡ƒ'鞧dÚn6(4)Œ•v–õk˜‡(4,4,6)-¡§dR2.1ÚR2.3Œ
•v‰'é(3,4,6)-¡=2§‰Ù¦3-¡–õ=
5
3
½
4
3
§‰z‡'é5-¡–õ=
1
3
,¤±
ch
∗
(v) ≥ch(v)−2×1−
5
3
×1−
4
3
×1−
1
3
×3 = 0.v؆(3,4,5)-¡ƒ'é§dR2.1ÚR2.3Œ•
v‰'é3-¡–õ=
5
3
§‰z‡'é5-¡–õ=
1
3
§¤±ch
∗
(v) ≥ch(v)−
5
3
×3−
1
3
×3 = 0"
œ¹5µd(v) ≥7§ch(v) = 2d(v)−6"-k•†vƒ'é3-¡Ú4-¡ƒêþ"
DOI:10.12677/aam.2019.891841584A^êÆ?Ð
ÜÊ
d51(1)(2)(4)(5)Υ
k≤b
d(v)
3
c(5)
q≤(k+b
d(v)−3k
2
c)−(t−k) = b
d(v)−3k
2
c+2k−t(6)
s≤d(v)−(t+q)−k(7)
d(1)ª§(4)ª§(5)ª§(6)ªÚ(7)ªŒ
ch
∗
(v) ≥2d(v)−6−(2t+
4
3
q+
1
3
s+
1
3
p)
≥d(v)−6−[2t+
4
3
q−
1
3
(d(v)−(t+q)−k)+
1
3
(d(v)−2×t−q)]
≥
4
3
d(v)−6−(t+
2
3
q−
1
3
k)
≥
4
3
d(v)−6−[t+
2
3
×(b
d(v)−3k
2
c+2k−t)−
1
3
k]
≥d(v)−6−
1
3
t.
ed(v)=2r+1§Ù¥r≥3§Kch
∗
(v)≥
5
3
r−5≥0¶ed(v)=2r§Ù¥r≥4§
Kch
∗
(v) ≥
5
3
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.891841585A^êÆ?Ð
ÜÊ
[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.891841586A^êÆ?Ð

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