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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematicsA^êÆ?Ð,2021,10(6),2249-2256
PublishedOnlineJune2021inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2021.106234
G¿éã©êDP-Úê
§§§JJJJJJ
úô“‰ŒÆêƆOŽÅ‰ÆÆ,úô7u
ÂvFϵ2021c528F¶¹^Fϵ2021c619F¶uÙFϵ2021c629F
Á‡
32015c§DP-/Ú(•éA/Ú)´dDvoˇr´akÚPostleJÑk'L/Úí2"32019
c§Bernshteyn§Kostochka§andZhuJÑDP-/Ú©ê‡"Ø”©êLÚ꧘
‡ãG©êDP-ÚêP•χ
∗
DP
(G)§Œ±?¿Œ'§©êÚê"G´˜ã¤¤8x§
§©êDP-Úê´ù㥩êDP-Úêþ(."·‚rŒ•–•t˜aG¿éãP
•Q
t
"ùŸØ©y²éut= 4q−1,4q,4q+1,4q+2§Q
t
©êDP-Úê•2+
1
q
"
'…c
©êDP-Ú꧌•§G¿éã
FractionalDP-ChromaticNumberof
Series-Parallel
RongrongWen
CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang
Received:May28
th
,2021;accepted:Jun.19
th
,2021;published:Jun.29
th
,2021
©ÙÚ^:§JJ.G¿éã©êDP-Úê[J].A^êÆ?Ð,2021,10(6):2249-2256.
DOI:10.12677/aam.2021.106234
§JJ
Abstract
DP-coloring(alsocalledcorrespondencecoloring)isgeneralizationoflistcoloringin-
troducedbyDvoˇr´akandPostlein2015.In2019,Bernshteyn§§§Kostochka§§§andZhu
intro ducedafractionalversionofDP-coloring.Unlikethefractionlistchromatic
number,thefractionalDP-chromaticnumberofagraphG§§§denotedχ
∗
DP
(G)§§§canbe
arbitrarilylargerthanχ
∗
(G).ThefractionalDP-chromaticnumberofafamilyGof
graphsisthesupremumofthefractionalDP-chromaticnumberofgraphsinG.We
denotebyQ
t
theclassofseries-parallelgraphswithgirthatleastt.Thispaperproves
thatfort= 4q−1,4q,4q+1,4q+2,thefractionalDP-chromaticnumberofQ
t
isexactly
2+
1
q
.
Keywords
FractionalDP-ChromaticNumb er,Girth,Series-ParallelGraph
Copyright
c
2021byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.Úó
ãG˜‡b--/Ú´•˜‡Nϕ§§‰Gz‡º:v©˜‡bôÚ8ϕ(v)⊆
{1,2,···,a}§÷vƒº:Â؃ôÚ8"G˜‡(a,b)-/Ú´•G˜‡b--/Ú
ϕ§¦éuz‡º:v÷vφ(v)⊆{1,2,···,a}"·‚¡G´(a,b)-Œ/…G¥•3˜‡
(a,b)-/Ú"G©êÚê•
χ
∗
(G) = inf{
a
b
: G´(a,b)-Œ/}”
G˜‡a-LDŠ´•˜‡NL§§‰Gz‡º:v©˜‡Œ^ôÚ8ÜL(v), G
˜‡b--L-/Ú´•G˜‡b--/Úϕ§¦éuz‡ º:v÷vφ(v)⊆L(v)"·‚¡G´
(a,b)-ŒÀ…éuG?¿˜‡a-LDŠ§G¥•3˜‡b--L-/Ú"G©êÀJÚê
•
χ
∗
`
(G) = inf{
a
b
: G´(a,b)-ŒÀ}”
DOI:10.12677/aam.2021.1062342250A^êÆ?Ð
§JJ
w,XJ˜‡ã´(a,b)-ŒÀ§@o§•´(a,b)-Œ/"Ïdχ
∗
(G) ≤χ
∗
`
(G). Alon,Tuza
ÚVoigt [1] y²éuk •ãG÷vχ
∗
(G)=χ
∗
`
(G)"…χ
∗
`
(G) ½Â¥e.Œ±^•Š5
“§ù¿›XXJ˜‡ãG´(a,b)-Œ/§@oéu,êm, G•´(am,bm)-ŒÀ"ù
pmÏ~ûuãG…˜„´˜‡éŒê"g,,·‚•Äùo˜‡¯Kµ´Äéz‡
(a,b)§é?¿êm, GÑ´(am,bm)-ŒÀErd˝os<ߎXJãG´(a,b)-ŒÀ§@o
é?¿êm∈N, G•´(am,bm)-ŒÀ"Tuza ÚVoigt[2] y²Tߎa=2 Úb= 1 ´
¤á§´§éu˜„œ¹§Tߎ3[3]¥‡y"
DP-/Ú´Dvoˇr´akÚPostle[4]éuL/Ú?1í2§GCX´•˜|kSé
H= (L,H)§d˜‡ãHÚ˜‡÷ve^‡¼êL: V(G) −→P(V(H))|¤µ
•V(G
L
)=
S
u∈V(G)
L
u
.
•é?¿u∈V(G), H[L(u)]´˜‡ã.
•eE
H
(L(u),L(v)) š˜,Ku= v½öuv∈E(G).
•euv∈E(G),KE
H
(L(u),L(v)) ´˜‡š(šŒU•˜).
eéuG¥z‡º:u÷v|L(u)|=m§K¡G˜‡CXH=(L,H) ´m--"
G˜‡H-/Ú´•3ãH¥é˜‡Õá8§ÙŒ•|V(G)|"Ï•éuz‡º:u§
H[L(u)]Ñ´˜‡㧷‚¡˜‡Õá8I⊆V(H) ´G˜‡H-/Ú…=éuz‡º
:u∈V(G)§÷v|I∩L(u)|= 1.GDP-Úêχ
DP
(G) ´÷vG•êm§¦GéÙ
z‡m--CXHÑk˜‡H-/Ú"
ã©êDP-ÚêVg´dBernshteyn,KostochkaÚZhu[5]JÑ"‰½ãGC
XH=(L,H)§·‚rH¥ëy©{L(v): v∈V(G)}ØÓÜ©>¡•>"eH[S] Ø
•¹>§K¡f8S⊆V(H)´[Õá"
eH=(L,H)´Ga--CX§b∈N…a≥b.G˜‡(H,b)-/Ú´••3˜‡[Õá
8S⊆V(H)§¦éz‡º:v∈V(G) ÷v|S∩L(v)|=b"·‚¡G´(H,b)-Œ/…G
¥k˜‡(H,b)-/Ú"éua,b∈N…a≥b§·‚¡ãG´(a,b)-DP-Œ/…éuGz‡
a--CXH, GÑ´(H,b)-Œ/"G©êDP-Úê•
χ
∗
DP
(G) = inf{
a
b
: G´(a,b)-DP-Œ/}”
ØJwÑXJãG´(a,b)-DP-Œ/§@oG•´(a,b)-ŒÀ§…z‡ãGÑ´
(χ
DP
(G),1)-DP-Œ/§ÏdŒ
χ
∗
(G) = χ
∗
`
(G) ≤χ
∗
DP
(G) ≤χ
DP
(G).
3[5] ¥•xχ
∗
DP
(G)=2 ãaµ˜‡º:êŒu½u2 ëÏãG÷vχ
∗
DP
(G)=2
…=G¥Ø•¹Û…•õ¹k˜‡ó.Ùg§XJGعÛ…fйk˜‡ó§K
éu?¿êb, GØ´(2b,b)-DP-Œ/§•Ò´`§éuχ
∗
DP
(G) ½Â¥e.´ØUˆ
"3[5]¥•y²XJ˜‡ã•Œ²þÝ÷vd≥4§Kχ
∗
DP
(G)≥d/(2lnd)"éuã
DOI:10.12677/aam.2021.1062342251A^êÆ?Ð
§JJ
©êDP-Úê3[6]¥•kïħ٥y²χ
∗
DP
(C
2r+1
) = 2+
1
r
"éu?¿n≥2 Úm∈N§•
3t∈N¦χ
∗
DP
(K
n,m
) ≤n+1−
1
t
"Óžm≥3 (½χ
∗
DP
(K
2,m
)e."
3ùŸØ©¥§·‚•ÄG¿éã©êDP-Úê"éuêk§-
Q
t
= {G: Gisaseries-parallelgraphwithgirthatleastk}.
ùŸØ©y²±e(J:
½n1bq´˜‡ê§éut∈{4q−1,4q,4q+1,4q+2}§χ
∗
DP
(Q
t
) = 2+
1
q
"
2.½n1y²
G¿éã´ã8ܧkX\ïÄ"¿…kŒþ d½Âéuùãa"ùŸØ©
̇^8B{§·‚æ^½Â§òØäéK
2
ÏLGÚ¿öŠ§/¤G¿éã"
½Â1(G;x,y)½Â•ÏLXe48öŠü‡à:G¿éã
•-V(K
2
) = {0,1}.@o(K
2
;0,1)´˜‡üà:G¿éã
•(¿öŠ) -(G;x,y) Ú(G
0
;x
0
,y
0
) ´:Øüà:G¿éã"ÏLrà:xÚx
0
¿•˜‡:
x
00
§¿…à:yÚy
0
¿•˜‡:y
00
§òãGÚG
0
Ü¿å5§ãG
00
"@o(G
00
;x
00
,y
00
)
´˜‡üà:G¿éã"
•(GöŠ)2-(G;x,y)and(G
0
;x
0
,y
0
)´:Øüà:G¿éã"ÏLr:yÚx
0
Ü¿•˜
‡:x
00
§òãGÚG
0
Ü¿å5§ãG
00
"@o(G
00
;x,y
0
)´˜‡üà:G¿éã"
XJ•3,ü‡:x, y¦(G;x,y)´˜‡üà:G¿éã§@où‡ã´˜‡G¿éã"
Ún1ba,k´˜‡ê¿…b´˜‡¢ê§¦a´˜‡ê§P
k
=
(v
0
,v
1
,...,v
k
) ´˜^´§¿…H=(L,H)´´P
k
˜‡(2a+ a)--CX§…|L(v
0
)|=a,
|L(v
i
)|= 2a+a(1 ≤i≤k)"éu0 ≤j≤k§•3L(v
j
)˜‡f8T
j
÷ve¡‡¦:
•XJj= 2m+1´Ûê,@o|T
j
|= a+a;XJj= 2m´óê,@o|T
j
|= a.
•éuL(v
j
) ¥÷v|B
j
∩T
j
|≥(1−m)a?¿a-f8B
j
§@o´P
j
=(v
0
,v
1
,...,v
j
) •
3˜‡(H,a)-/Úφ¦:v
j
/8ÜB
j
¥ôÚ§P•φ(v
j
) = B
j
"
y²éj?18Bb§XJj=0§@o-T
0
=L(v
0
)§XJj=1§@o-T
1
=
L(v
1
)−N
H
(T
0
)"ù‡(Jw,´¤á"
bj≥2 §¿…éuj
0
<jù‡Ún¤á"
œ¹1j= 2m•óê"
d8BbŒ§3L(v
2m−1
) ¥•3˜‡(a+a) -f8T
2m−1
,¦áu8 ÜL(v
2m−1
) ¥
?¿a-f 8 B
2m−1
§k|B
2m−1
∩T
2m−1
|≥(1−(m−1))a¤á"éu´P
2m−1
þ/Ú§•3
˜‡(H,a)-/Úφ§¦:v
2m−1
/8ÜB
2m−1
¥ôÚ§P•φ(v
2m−1
) = B
2m−1
"
-T
0
2m−1
´8ÜT
2m−1
3L(v
2m
) ¥¤šôÚ§ •Ò´`T
0
2m−1
=N
H
(T
2m−1
)∩L(v
2m
)
"Ø”˜„5§·‚Œ±b|T
0
2m−1
|=a+ a§Ï•|L(v
2m
)|=(2 + )a§·‚k|L(v
2m
) −
DOI:10.12677/aam.2021.1062342252A^êÆ?Ð
§JJ
T
2m−1
|≥a"-T
2m
´L(v
2m
)−T
2m−1
¥?¿a-f8"bB
2m
´L(v
2m
)¥a-8Ü…÷v
|B
2m
∩T
2m
|≥(1−m)a"·‚ATy²´P
2m
•3˜‡(H,a)-/Úφ¦φ(v
2m
) = B
2m
"
®•|B
2m
∩T
0
2m−1
|≤a−(1−m)a= ma"¤±|T
0
2m−1
−B
2m
|≥(1−(m−1))a"
-B
0
2m
= N
H
(B
2m
)∩L(v
2m−1
)§Ï•|T
0
2t−1
−B
2m
|≥(1−(m−1))a§@oL(v
2m−1
)−B
0
2m
¥•3˜‡•¹(1 −(m−1))aôÚa-8ÜB
2m−1
"ÏL8Bb§´P
2m−1
•3˜‡
(H,a) -/Úφ§…¦:v
2m−1
/8ÜB
2m−1
¥ôÚ§P•φ(v
2m−1
)= B
2m−1
"=/ÚφŒ
±òÿ´P
2m
þ(H,a)-/Ú§…:v
2m
/8ÜB
2m
¥ôÚ,P•φ(v
2m
) = B
2m
"
œ¹2j= 2m+1 ´Ûê
d8BbŒ§L(v
2m
) ¥•3˜‡a-f8T
2m
§¦éuL(v
2m
) ¥÷v|B
2m
∩T
2m
|≥
(1−m)a?¿a-f8B
2m
§´P
2m
•3˜‡(H,a)-/Úφ§…:v
2m
/8ÜB
2m
¥ôÚ§P•φ(v
2m
)=B
2m
"-T
0
2m
´8ÜL(v
2m+1
)¥†T
2m
šôÚ"•Ò´`
T
0
2m
= N
H
(T
2m
)∩L(v
2m+1
)"·‚b|T
0
2m
|= a§Œ|L(v
2m+1
)−T
0
2m
|= (1+)a"-T
2m+1
´
L(v
2m+1
)−T
2m
¥?¿(1+)a-8Ü"bB
2m+1
´L(v
2m+1
)¥÷v|B
2m+1
∩T
2m+1
|≥(1−m)a
a-8Ü"·‚AT‡y²´P
2m+1
•3˜‡(H,a)-/Úφ…¦:v
2m+1
/8ÜB
2m+1
¥
ôÚ§P•φ(v
2m+1
) = B
2m+1
"
®•|B
2m+1
∩T
0
2m
|≤(1−m)a§¤±|T
0
2m
−B
2m+1
|≥(1−m)a"
-B
0
2m+1
=N
H
(B
2m+1
)∩L(v
2m
)"b|B
0
2m+1
|=a"@oL(v
2m
)−B
0
2m+1
•3˜‡•¹
T
2m
¥(1−m)aôÚa-8Ü"ÏL8Bb§´P
2m
•3˜‡(H,a) -/Úφ§…¦:
v
2m+1
/8ÜB
2m+1
¥ôÚ,P•φ(v
2m+1
) = B
2m+1
"
íØ1ba,k´ê§-
=







2
k−1
,ifkisodd
2
k
,ifkiseven.
XJP
k
= (v
0
,v
1
,...,v
k
) ´˜^••k´§¿…H=(L,H)´G˜‡(2a+a) --CX"´
P
k
þÄ—ü:L••a§P•|L(v
0
)|= |L(v
k
)|= a§éuÙ¦:L••2a+a§P
•|L(v
i
)|= 2a+a( 1 ≤i≤k−1 )"@o•3´P
k
þ˜‡(H,a)-/Úφ"
y²·‚rù‡y²©•ü«œ¹µ
œ¹1k= 2m•óê
ÏLÚn1Œ§•3LL(v
k−1
)þ••(a+ a)f8T
k−1
§¦éuL(v
k−1
)þ÷
v|B
k−1
∩T
k−1
|≥(1 −(m−1))a?¿a-f8B
k−1
§´P
k−1
=(v
0
,v
1
,...v
k−1
) •3˜‡
(H,a) -/Úφ§…¦:v
k−1
/8ÜB
k−1
¥ôÚ§P•φ(v
k−1
)=B
k−1
"Ï•ta=a§·
‚k|T
k−1
−L(v
k
)|≥a= (1−(m−1))a"Ïd3L(v
k−1
)−L(v
k
) þ•3a-f8B
k−1
§•
¹T
k−1
¥–(1−(m−1))a‡ôÚ"dÚn1Œ§´P
k−1
•3˜‡(H,a) -/Úφ…÷v
φ(v
k
) = L(v
k
)"
œ¹2k= 2m+1•Ûê
-B´L(v
k−1
) −L(v
k
)a-f8"éu1≤i≤k−2§-L
0
(v
i
)=L(v
i
)§¿…-
DOI:10.12677/aam.2021.1062342253A^êÆ?Ð
§JJ
L
0
(v
k−1
) =B"dœ¹1Œ´P
k−1
= (v
0
,v
1
,...v
k−1
) k˜‡(H,a)-/Úφ§…÷v:v
k−1
/8
ÜB¥ôÚ§ P•φ(v
k−1
) =B"y3φŒ±òÿ´P
k
þ˜‡(H,a)-/Ú§…¦:v
k
/8ÜB
k
¥ôÚ§P•φ(v
k
) = L(v
k
)"
Ún2[7]XJ(G;x,y) ´˜‡Œ•–•tG¿é㧅k= dt/2e,KG‡o´˜^
´§‡oÒ•¹˜^••k´P=(v
0
,v
1
,...,v
k
) §¦G¥¤k:v
1
,v
2
,...,v
k−1
Ý•2"
…§‚Ñ´à:x½öy"
y²bG•¹˜‡C"XJG=C§Ï•CkŒ•–•t§@où‡(Ø´é
"‡ƒ§(G
1
;x
1
,y
1
)Ú(G
2
;x
2
,y
2
)ÏL˜XG¿éE(G;x,y)"XJ(G
1
;x
1
,y
1
)Ú
(G
2
;x
2
,y
2
) Ù¥˜‡•¹˜‡§@oG
1
½G
2
•¹˜^÷v‡¦´"‡ƒ§Ï•G•¹˜‡
§(G;x,y) Œd(G
1
;x
1
,y
1
) Ú(G
2
;x
2
,y
2
) ¿é"éui=1,2 , G
i
´˜^ ´ëx
i
Úy
i
"
@oG´˜‡§¿…ù‡(ؤá"
½n2bq,a´˜‡ê§éu?¿Œ•–•tG¿éãG§t∈{4q−
1,4q,4q+1,4q+2}ž§G´((2+
1
q
)a,a)-DP-/Ú"
y²bH= (L,H) ´G((2+
1
q
)a)--CX"·‚I‡`²Gk˜‡(H,a)-/Ú"ù
‡y²ÏLéG¥:ê8?18B"XJG´˜^´§@oG´(2a,a)-DP-Œ/§¿…(
Ø"bGØ´˜^´"ÏLÚn2§Gk˜^••k´P= (v
0
,v
1
,...,v
k
)(t∈{4q−1,4q}
ž§@ok=2q;t∈{4q+ 1,4q+2},@ok=2q+ 1) §¦G¥¤k:v
1
,v
2
,...,v
k−1
Ý•2.-G
0
=G−{v
1
,v
2
,...,v
k−1
}"@oG
0
´˜‡Œ•–•4q−1G¿é㧽ö
G
0
´˜^´"bG
0
´˜‡Œ•–•4q−1G¿éã§@oÏL8Bb§G
0
k˜‡
(H,a)-/Úφ"XJG
0
´˜^´§Ï•´´(2a,a)-DP-/Ú§@oG
0
k˜‡(H,a)-/Úφ"-
H
0
= (L
0
,H) ´´P= (v
0
,v
1
,...,v
k
) ((2+
1
q
)a) --CX§…éu´P= (v
0
,v
1
,...,v
k
) þ:
÷vL
0
(v
l
) = φ(v
l
)¿…éu1 ≤i≤l−1§L
0
(v
i
) = L(v
i
)"ÏLíØ1§Pk˜‡(H,a) -/Úφ"
@oφÚψÜå5Ò´ãG˜‡(H,a)-/Ú"
ÏL½n2§éut∈{4q−1,4q,4q+1,4q+2}§Q
t
©êDP-Úê´–õ2 +
1
q
"•`
²ù‡ª¤á§·‚I‡E§éuz‡êa§˜‡ãáuQ
t
§§Ø´((2+
1
q
)a−1,a)
-DP-/Ú"
Ún3ba, k´˜‡ê¿…b´˜‡¢ê§¦a´˜‡ê…
<



2
k−1
,ifkisodd
2
k
,ifkiseven.
-P
k
= (v
0
,v
1
,...,v
k
)´˜^´.-X
1
,X
2
´a-8Ü.@o´P
k
•3˜‡CXH= (L,H)…±
e^‡Ñ‡÷vµ
•L(v
0
) = X
1
§L(v
l
) = X
2
•|L(v
i
)|= 2a+a(1 ≤i≤k−1)
•´P
k
Ø´(H,a)-/Ú
y²-M
f
(f=1,3,5,...,2q−3), N
g
(g=2,4,6,...,2q−2), Z
h
(h=1,3,5,...,2q−1)´
؃ôÚ8§…|M
f
|= |N
g
|= a,|Z
h
|= a.-H= (L,H)´´P
k
þ˜‡CX§½ÂXe
DOI:10.12677/aam.2021.1062342254A^êÆ?Ð
§JJ
•L(v
0
) = X
1
,L(v
l
) = X
2
,L(v
1
) = X
1
∪M
1
∪Z
1
.
•|L(v
2i+1
)|= N
2i
∪M
2i+1
∪Z
2i+1
,i= 1,2,3,...,q−2.
•|L(v
2j
)|= N
2j
∪M
2j−1
∪Z
2j−1
,j= 1,2,3,...,q−1.
•XJk= 2q,@oL(v
2q−1
) =X
2
∪N
2q−2
∪Z
2q−1
;XJk= 2q+1,@oL(v
2q
) =X
2
∪M
2q−1
∪
Z
2q−1
.
·‚AT‡y²P
k
Ø´(H,a)-/Ú
äó1éu?¿j∈{2,3,4,...,q}§XJφ´´P
2j−2
þ˜‡(H,a)-/Ú§@o|φ(v
2j−2
)∩
N
2j−2
|≥a−(j−1)a"
y²·‚ e5éeIj?18Bb§?¤ù‡y²"bj=2¿…φ´´P
2
þ
˜‡(H,a)-/Ú"Ï•φ(v
0
) = X
1
§·‚Œ±φ(v
1
) ⊆M
1
∪Z
1
"K|φ(v
2
)∩(M
1
∪Z
1
)|≤a"
Ïd|φ(v
2
)∩N
2
|≥a−a"
bj≥3¿…ù‡äóéuj
0
<j¤á"φ´´P
2j−2
þ˜‡(H,a)-/Ú"é´P
2j−4
þ
/Úφ•›A^8Bb§·‚Œ±
|φ(v
2j−4
)∩N
2j−4
|≥a−(j−2)a
K|φ(v
2j−3
)∩N
2j−4
|≤(j−2)a"ddŒí
|φ(v
2j−3
)∩(M
2j−3
∪Z
2j−3
)|≥a−(j−2)a
Ïd
|φ(v
2j−2
)∩(M
2j−3
∪Z
2j−3
)|≤(j−1)a
l|φ(v
2j−2
)∩N
2j−2
|≥a−(j−1)a
bk=2q´˜‡ó꧿…´φ´´P
2q
˜‡(H,a) -/Ú"@o|φ(v
2q−2
) ∩N
2q−2
|≥
a−(q−1)a"Ï•φ(v
2q
)=X
2
§·‚Œ±φ(v
2q−1
)⊆(N
2q−2
−φ(v
2q−2
))∪Z
2q−1
"´
|(N
2q−2
−φ(v
2q−2
))∪Z
2q−1
|≤(q−1)a+a= qa<a§K:v
2q−1
Œ/a‡ôÚ†:v
2q−2
/
ôÚ7½ƒ§gñ"
bk= 2q+1´˜‡Û꧅φ´´P
2q+1
˜‡(H,a)-/Ú"däó1Œ•§|φ(v
2q−2
)∩
N
2q−2
|≥a−(q−1)a"Ïd|φ(v
2q−1
)∩N
2q−2
|≤(q−1)a"Ï•φ(v
2q+1
) = X
2
"¤±φ(v
2q
) ⊆
(M
2q−1
∪Z
2q−1
)−φ(v
2q−1
)"´|(M
2q−1
∪Z
2q−1
)−φ(v
2q−1
)|≤a+a−(a−(q−1)a) = qa<a"
dd·‚:v
2q
Œ/a‡ôÚ†:v
2q−1
/ôÚ7½ƒ§gñ"
½n3bq§a´˜‡꧿…b´˜‡¢ê§ ¦a´˜‡꧅<
1
q
"
éuk∈{4q−1,4q,4q+1,4q+2}§@o•3˜‡ãG∈Q
t
,¦GØ´((2+)a,a-/Ú"
y²-p=

(2+)a
a

2
"-GdŒ••

t
2

´¿E§ü‡à:P•xÚy§@o
G∈Q
t
"
·‚ATy²GØ´((2 + )a,a)-/Ú"-XÚY´¹k(2a+ a) ƒ8ܧ¿…-
L(x) =XandL(y)=Y"@oÒkp«(H,a)-/Ú•ª"z«/ÚφÑéA˜^Œ••

t
2


´"3z^´§½Â(H,a)ÓÚn3CX§X
1
^φ(x)O“§Y
1
^φ(y)O“"@odÚn3Œ
DOI:10.12677/aam.2021.1062342255A^êÆ?Ð
§JJ
§3xÚy þ(H,a) -/ÚØŒ±òÿ‡ãG/Ú"
ÏL½n3 §éuk∈{4q−1,4q,4q+1,4q+2}§ãaQ
t
©êDP-/Úê–´2+
1
q
"
(ܽn2§K¤½n1 y²"
ë•©z
[1]Alon,N.,Tuza,Z.andVoigt,M.(1997)ChoosabilityandFractionalChromaticNumbers.
DiscreteMathematics,165-166,31-38.https://doi.org/10.1016/S0012-365X(96)00159-8
[2]Tuza,Z.andVoigt,M.(1996)Every2-ChoosableGraphIs(2m,m)-Choosable.Journalof
GraphTheory,22,245-252.
https://doi.org/10.1002/(SICI)1097-0118(199607)22:3h245::AID-JGT5i3.0.CO;2-M
[3]Dvoˇr´ak, Z., Hu, X.andSereni, H.-S. (2018)A4-Choosable GraphThat IsNot (8:2)-Choosable.
arXiv:1806.03880(preprint).
[4]DvoˇrSk, Z. and Postle, L. (2018)Correspondence Coloring andIts Application toList-Coloring
PlanarGraphswithoutCyclesofLengths4to8.JournalofCombinatorialTheory,SeriesB,
129,38-54.https://doi.org/10.1016/j.jctb.2017.09.001
[5]Bernshteyn,A.,Kostochka,A.andZhu,X.(2020)FractionalDP-ColoringofSparseGraphs.
JournalofGraphTheory,93,203-221.https://doi.org/10.1002/jgt.22482
[6]Kaul,H.andMudrock,J.(2019)ANoteonFractionalDP-ColoringofGraphs.arX-
iv:1904.07697(preprint).
[7]Li,X.E.andZhu,X.(2020)TheStrongFractionalChoiceNumberofSeries-ParallelGraphs.
DiscreteMathematics,343,ArticleID:111796.https://doi.org/10.1016/j.disc.2019.111796
DOI:10.12677/aam.2021.1062342256A^êÆ?Ð

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