设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投稿
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
AdvancesinAppliedMathematics
A^
ê
Æ
?
Ð
,2021,10(6),2249-2256
PublishedOnlineJune2021inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2021.106234
G
¿
é
ã
©
ê
DP
-
Ú
ê
§§§
JJJJJJ
ú
ô
“
‰
Œ
Æ
ê
Æ
†
O
Ž
Å
‰
ÆÆ
,
ú
ô
7
u
Â
v
F
Ï
µ
2021
c
5
28
F
¶
¹
^
F
Ï
µ
2021
c
6
19
F
¶
u
Ù
F
Ï
µ
2021
c
6
29
F
Á
‡
3
2015
c
§
DP-
/Ú
(
•
é
A
/Ú
)
´
d
Dvo
ˇ
r
´
ak
Ú
Postle
J
Ñ
k
'
L
/Ú
í
2
"
3
2019
c
§
Bernshteyn
§
Kostochka
§
and
Zhu
J
Ñ
DP-
/Ú
©
ê
‡
"
Ø
”
©
ê
L
Ú
ê
§
˜
‡
ã
G
©
ê
DP
-
Ú
ê
P
•
χ
∗
DP
(
G
)
§
Œ
±
?
¿
Œ
'
§
©
ê
Ú
ê
"
G
´
˜
ã
¤
¤
8
x
§
§
©
ê
DP
-
Ú
ê´
ù
ã
¥
©
ê
DP
-
Ú
ê
þ(
.
"
·
‚
r
Œ
•
–
•
t
˜
a
G
¿
é
ã
P
•
Q
t
"
ù
Ÿ
Ø
©
y
²
é
u
t
= 4
q
−
1
,
4
q,
4
q
+1
,
4
q
+2
§
Q
t
©
ê
DP
-
Ú
ê
•
2+
1
q
"
'
…
c
©
ê
DP
-
Ú
ê
§
Œ
•
§
G
¿
é
ã
Fractional
DP
-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-
troducedby
Dvo
ˇ
r
´
ak
and
Postle
in2015.In2019,Bernshteyn
§§§
Kostochka
§§§
andZhu
intro ducedafractionalversionofDP-coloring.Unlikethefractionlistchromatic
number,thefractionalDP-chromaticnumberofagraph
G
§§§
denoted
χ
∗
DP
(
G
)
§§§
canbe
arbitrarilylargerthan
χ
∗
(
G
)
.ThefractionalDP-chromaticnumberofafamily
G
of
graphsisthesupremumofthefractionalDP-chromaticnumberofgraphsin
G
.We
denoteby
Q
t
theclassofseries-parallelgraphswithgirthatleast
t
.Thispaperproves
thatfor
t
= 4
q
−
1
,
4
q,
4
q
+1
,
4
q
+2
,thefractionalDP-chromaticnumberof
Q
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
-
-
/Ú
ϕ
§
¦
é
u
z
‡
º:
v
÷
v
φ
(
v
)
⊆{
1
,
2
,
···
,a
}
"
·
‚
¡
G
´
(
a,b
)-
Œ
/
…
G
¥
•
3
˜
‡
(
a,b
)-
/Ú
"
G
©
ê
Ú
ê
•
χ
∗
(
G
) = inf
{
a
b
:
G
´
(
a,b
)-
Œ
/
}
”
G
˜
‡
a
-
L
D
Š
´
•
˜
‡
N
L
§
§
‰
G
z
‡
º:
v
©
˜
‡
Œ
^
ô
Ú
8
Ü
L
(
v
),
G
˜
‡
b
-
-
L
-
/Ú
´
•
G
˜
‡
b
-
-
/Ú
ϕ
§
¦
é
u
z
‡
º:
v
÷
v
φ
(
v
)
⊆
L
(
v
)
"
·
‚
¡
G
´
(
a,b
)-
Œ
À
…
é
u
G
?
¿˜
‡
a
-
L
D
Š
§
G
¥
•
3
˜
‡
b
-
-
L
-
/Ú
"
G
©
ê
À
J
Ú
ê
•
χ
∗
`
(
G
) = inf
{
a
b
:
G
´
(
a,b
)-
Œ
À
}
”
DOI:10.12677/aam.2021.1062342250
A^
ê
Æ
?
Ð
§
JJ
w
,X
J
˜
‡
ã
´
(
a,b
)-
Œ
À
§
@
o
§
•
´
(
a,b
)-
Œ
/
"
Ï
d
χ
∗
(
G
)
≤
χ
∗
`
(
G
). Alon,Tuza
Ú
Voigt [1]
y
²
é
uk
•
ã
G
÷
v
χ
∗
(
G
)=
χ
∗
`
(
G
)
"
…
χ
∗
`
(
G
)
½
Â
¥
e
.
Œ
±
^
•
Š
5
“
§
ù
¿
›
X
X
J
˜
‡
ã
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
<
ß
Ž
X
J
ã
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
´
•
˜
|
k
S
é
H
= (
L,H
)
§
d
˜
‡
ã
H
Ú
˜
‡
÷
v
e
^
‡
¼
ê
L
:
V
(
G
)
−→
P
(
V
(
H
))
|
¤
µ
•
V
(
G
L
)=
S
u
∈
V
(
G
)
L
u
.
•
é
?
¿
u
∈
V
(
G
),
H
[
L
(
u
)]
´
˜
‡
ã
.
•
e
E
H
(
L
(
u
)
,L
(
v
))
š
˜
,
K
u
=
v
½
ö
uv
∈
E
(
G
).
•
e
uv
∈
E
(
G
),
K
E
H
(
L
(
u
)
,L
(
v
))
´
˜
‡
š
(
š
Œ
U
•
˜
).
e
é
u
G
¥
z
‡
º:
u
÷
v
|
L
(
u
)
|
=
m
§
K
¡
G
˜
‡CX
H
=(
L,H
)
´
m
-
-
"
G
˜
‡
H
-
/Ú
´
•
3
ã
H
¥
é
˜
‡
Õ
á
8
§
Ù
Œ
•
|
V
(
G
)
|
"
Ï
•
é
u
z
‡
º:
u
§
H
[
L
(
u
)]
Ñ
´
˜
‡
ã
§
·
‚
¡
˜
‡
Õ
á
8
I
⊆
V
(
H
)
´
G
˜
‡
H
-
/Ú
…
=
é
u
z
‡
º
:
u
∈
V
(
G
)
§
÷
v
|
I
∩
L
(
u
)
|
= 1.
G
DP
-
Ú
ê
χ
DP
(
G
)
´
÷
v
G
•
ê
m
§
¦
G
é
Ù
z
‡
m
-
-
CX
H
Ñ
k
˜
‡
H
-
/Ú
"
ã
©
ê
DP
-
Ú
ê
V
g
´
d
Bernshteyn,Kostochka
Ú
Zhu[5]
J
Ñ
"
‰
½
ã
G
C
X
H
=(
L,H
)
§
·
‚
r
H
¥
ë
y
©
{
L
(
v
):
v
∈
V
(
G
)
}
Ø
Ó
Ü
©
>
¡
•
>
"
e
H
[
S
]
Ø
•
¹
>
§
K
¡
f
8
S
⊆
V
(
H
)
´
[
Õ
á
"
e
H
=(
L,H
)
´
G
a
-
-
CX
§
b
∈
N
…
a
≥
b
.
G
˜
‡
(
H
,b
)-
/Ú
´
•
•
3
˜
‡
[
Õ
á
8
S
⊆
V
(
H
)
§
¦
é
z
‡
º:
v
∈
V
(
G
)
÷
v
|
S
∩
L
(
v
)
|
=
b
"
·
‚
¡
G
´
(
H
,b
)-
Œ
/
…
G
¥
k
˜
‡
(
H
,b
)-
/Ú
"
é
u
a,b
∈
N
…
a
≥
b
§
·
‚
¡
ã
G
´
(
a,b
)-
DP
-
Œ
/
…
é
u
G
z
‡
a
-
-
CX
H
,
G
Ñ
´
(
H
,b
)-
Œ
/
"
G
©
ê
DP
-
Ú
ê
•
χ
∗
DP
(
G
) = inf
{
a
b
:
G
´
(
a,b
)-
DP
-
Œ
/
}
”
Ø
J
w
Ñ
X
J
ã
G
´
(
a,b
)-
DP
-
Œ
/
§
@
o
G
•
´
(
a,b
)-
Œ
À
§
…
z
‡
ã
G
Ñ
´
(
χ
DP
(
G
)
,
1)-
DP
-
Œ
/
§
Ï
d
Œ
χ
∗
(
G
) =
χ
∗
`
(
G
)
≤
χ
∗
DP
(
G
)
≤
χ
DP
(
G
)
.
3
[5]
¥
•
x
χ
∗
DP
(
G
)=2
ã
a
µ
˜
‡
º:
ê
Œ
u
½
u
2
ë
Ïã
G
÷
v
χ
∗
DP
(
G
)=2
…
=
G
¥
Ø
•
¹
Û
…
•
õ
¹
k
˜
‡
ó
.
Ù
g
§
X
J
G
Ø
¹
Û
…
f
й
k
˜
‡
ó
§
K
é
u
?
¿
ê
b
,
G
Ø
´
(2
b,b
)-
DP
-
Œ
/
§
•
Ò
´
`
§
é
u
χ
∗
DP
(
G
)
½
Â
¥
e
.
´
Ø
U
ˆ
"
3
[5]
¥
•
y
²
X
J
˜
‡
ã
•
Œ
²
þ
Ý
÷
v
d
≥
4
§
K
χ
∗
DP
(
G
)
≥
d/
(2ln
d
)
"
é
u
ã
DOI:10.12677/aam.2021.1062342251
A^
ê
Æ
?
Ð
§
JJ
©
ê
DP
-
Ú
ê
3
[6]
¥
•
k
ï
Ä
§
Ù
¥y
²
χ
∗
DP
(
C
2
r
+1
) = 2+
1
r
"
é
u
?
¿
n
≥
2
Ú
m
∈
N
§
•
3
t
∈
N
¦
χ
∗
DP
(
K
n,m
)
≤
n
+1
−
1
t
"
Ó
ž
m
≥
3
(
½
χ
∗
DP
(
K
2
,m
)
e
.
"
3ù
Ÿ
Ø
©
¥
§
·
‚
•
Ä
G
¿
é
ã
©
ê
DP-
Ú
ê
"
é
u
ê
k
§
-
Q
t
=
{
G
:
G
isaseries-parallelgraphwithgirthatleast
k
}
.
ù
Ÿ
Ø
©
y
²
±
e
(
J
:
½
n
1
b
q
´
˜
‡
ê
§
é
u
t
∈{
4
q
−
1
,
4
q,
4
q
+1
,
4
q
+2
}
§
χ
∗
DP
(
Q
t
) = 2+
1
q
"
2.
½
n
1
y
²
G
¿
é
ã
´
ã
8
Ü
§
k
X
\
ï
Ä
"
¿
…
k
Œ
þ
d
½
Â
é
u
ù
ã
a
"
ù
Ÿ
Ø
©
Ì
‡
^
8
B
{
§
·
‚
æ
^
½
Â
§
ò
Ø
äé
K
2
Ï
L
G
Ú
¿
ö
Š
§
/
¤
G
¿
é
ã
"
½
Â
1
(
G
;
x,y
)
½
Â
•
Ï
L
X
e
4
8
ö
Š
ü
‡
à:
G
¿
é
ã
•
-
V
(
K
2
) =
{
0
,
1
}
.
@
o
(
K
2
;0
,
1)
´
˜
‡
ü
à:
G
¿
é
ã
•
(
¿ö
Š
)
-
(
G
;
x,y
)
Ú
(
G
0
;
x
0
,y
0
)
´
:
Ø
ü
à:
G
¿
é
ã
"
Ï
L
r
à:
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
¿
é
ã
"
Ï
L
r
:
y
Ú
x
0
Ü
¿
•
˜
‡
:
x
00
§
ò
ã
G
Ú
G
0
Ü
¿
å
5
§
ã
G
00
"
@
o
(
G
00
;
x,y
0
)
´
˜
‡
ü
à:
G
¿
é
ã
"
X
J
•
3
,
ü
‡
:
x, y
¦
(
G
;
x,y
)
´
˜
‡
ü
à:
G
¿
é
ã
§
@
o
ù
‡
ã
´
˜
‡
G
¿
é
ã
"
Ú
n
1
b
a
,
k
´
˜
‡
ê
¿
…
b
´
˜
‡
¢ê
§
¦
a
´
˜
‡
ê
§
P
k
=
(
v
0
,v
1
,...,v
k
)
´
˜
^
´
§
¿
…
H
=(
L,H
)
´
´
P
k
˜
‡
(2
a
+
a
)-
-
CX
§
…
|
L
(
v
0
)
|
=
a
,
|
L
(
v
i
)
|
= 2
a
+
a
(1
≤
i
≤
k
)
"
é
u
0
≤
j
≤
k
§
•
3
L
(
v
j
)
˜
‡
f
8
T
j
÷
v
e
¡
‡
¦
:
•
X
J
j
= 2
m
+1
´
Û
ê
,
@
o
|
T
j
|
=
a
+
a
;
X
J
j
= 2
m
´
ó
ê
,
@
o
|
T
j
|
=
a
.
•
é
u
L
(
v
j
)
¥
÷
v
|
B
j
∩
T
j
|≥
(1
−
m
)
a
?
¿
a
-
f
8
B
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
?
1
8
B
b
§
X
J
j
=0
§
@
o
-
T
0
=
L
(
v
0
)
§
X
J
j
=1
§
@
o
-
T
1
=
L
(
v
1
)
−
N
H
(
T
0
)
"
ù
‡
(
J
w
,
´
¤
á
"
b
j
≥
2
§
¿
…
é
u
j
0
<j
ù
‡
Ú
n
¤
á
"
œ
¹
1
j
= 2
m
•
ó
ê
"
d
8
B
b
Œ
§
3
L
(
v
2
m
−
1
)
¥
•
3
˜
‡
(
a
+
a
) -
f
8
T
2
m
−
1
,
¦
á
u
8
Ü
L
(
v
2
m
−
1
)
¥
?
¿
a-
f
8
B
2
m
−
1
§
k
|
B
2
m
−
1
∩
T
2
m
−
1
|≥
(1
−
(
m
−
1)
)
a
¤
á
"
é
u
´
P
2
m
−
1
þ
/Ú
§
•
3
˜
‡
(
H
,a
)-
/Ú
φ
§
¦
:
v
2
m
−
1
/
8
Ü
B
2
m
−
1
¥
ô
Ú
§
P
•
φ
(
v
2
m
−
1
) =
B
2
m
−
1
"
-
T
0
2
m
−
1
´
8
Ü
T
2
m
−
1
3
L
(
v
2
m
)
¥
¤
š
ô
Ú
§
•
Ò
´
`
T
0
2
m
−
1
=
N
H
(
T
2
m
−
1
)
∩
L
(
v
2
m
)
"
Ø
”
˜
„
5
§
·
‚
Œ
±
b
|
T
0
2
m
−
1
|
=
a
+
a
§
Ï
•
|
L
(
v
2
m
)
|
=(2 +
)
a
§
·
‚
k
|
L
(
v
2
m
)
−
DOI:10.12677/aam.2021.1062342252
A^
ê
Æ
?
Ð
§
JJ
T
2
m
−
1
|≥
a
"
-
T
2
m
´
L
(
v
2
m
)
−
T
2
m
−
1
¥
?
¿
a
-
f
8
"
b
B
2
m
´
L
(
v
2
m
)
¥
a
-
8
Ü
…
÷
v
|
B
2
m
∩
T
2
m
|≥
(1
−
m
)
a
"
·
‚
A
T
y
²
´
P
2
m
•
3
˜
‡
(
H
,a
)-
/Ú
φ
¦
φ
(
v
2
m
) =
B
2
m
"
®
•
|
B
2
m
∩
T
0
2
m
−
1
|≤
a
−
(1
−
m
)
a
=
ma
"
¤
±
|
T
0
2
m
−
1
−
B
2
m
|≥
(1
−
(
m
−
1)
)
a
"
-
B
0
2
m
=
N
H
(
B
2
m
)
∩
L
(
v
2
m
−
1
)
§
Ï
•
|
T
0
2
t
−
1
−
B
2
m
|≥
(1
−
(
m
−
1)
)
a
§
@
o
L
(
v
2
m
−
1
)
−
B
0
2
m
¥
•
3
˜
‡
•
¹
(1
−
(
m
−
1)
)
a
ô
Ú
a
-
8
Ü
B
2
m
−
1
"
Ï
L8
B
b
§
´
P
2
m
−
1
•
3
˜
‡
(
H
,a
) -
/Ú
φ
§
…
¦
:
v
2
m
−
1
/
8
Ü
B
2
m
−
1
¥
ô
Ú
§
P
•
φ
(
v
2
m
−
1
)=
B
2
m
−
1
"
=
/Ú
φ
Œ
±
ò
ÿ
´
P
2
m
þ
(
H
,a
)-
/Ú
§
…
:
v
2
m
/
8
Ü
B
2
m
¥
ô
Ú
,
P
•
φ
(
v
2
m
) =
B
2
m
"
œ
¹
2
j
= 2
m
+1
´
Û
ê
d
8
B
b
Œ
§
L
(
v
2
m
)
¥
•
3
˜
‡
a
-
f
8
T
2
m
§
¦
é
u
L
(
v
2
m
)
¥
÷
v
|
B
2
m
∩
T
2
m
|≥
(1
−
m
)
a
?
¿
a
-
f
8
B
2
m
§
´
P
2
m
•
3
˜
‡
(
H
,a
)-
/Ú
φ
§
…
:
v
2
m
/
8
Ü
B
2
m
¥
ô
Ú
§
P
•
φ
(
v
2
m
)=
B
2
m
"
-
T
0
2
m
´
8
Ü
L
(
v
2
m
+1
)
¥
†
T
2
m
š
ô
Ú
"
•
Ò
´
`
T
0
2
m
=
N
H
(
T
2
m
)
∩
L
(
v
2
m
+1
)
"
·
‚
b
|
T
0
2
m
|
=
a
§
Œ
|
L
(
v
2
m
+1
)
−
T
0
2
m
|
= (1+
)
a
"
-
T
2
m
+1
´
L
(
v
2
m
+1
)
−
T
2
m
¥
?
¿
(1+
)
a
-
8
Ü
"
b
B
2
m
+1
´
L
(
v
2
m
+1
)
¥
÷
v
|
B
2
m
+1
∩
T
2
m
+1
|≥
(1
−
m
)
a
a
-
8
Ü
"
·
‚
A
T
‡
y
²
´
P
2
m
+1
•
3
˜
‡
(
H
,a
)-
/Ú
φ
…
¦
:
v
2
m
+1
/
8
Ü
B
2
m
+1
¥
ô
Ú
§
P
•
φ
(
v
2
m
+1
) =
B
2
m
+1
"
®
•
|
B
2
m
+1
∩
T
0
2
m
|≤
(1
−
m
)
a
§
¤
±
|
T
0
2
m
−
B
2
m
+1
|≥
(1
−
m
)
a
"
-
B
0
2
m
+1
=
N
H
(
B
2
m
+1
)
∩
L
(
v
2
m
)
"
b
|
B
0
2
m
+1
|
=
a
"
@
o
L
(
v
2
m
)
−
B
0
2
m
+1
•
3
˜
‡
•
¹
T
2
m
¥
(1
−
m
)
a
ô
Ú
a
-
8
Ü
"
Ï
L8
B
b
§
´
P
2
m
•
3
˜
‡
(
H
,a
) -
/Ú
φ
§
…
¦
:
v
2
m
+1
/
8
Ü
B
2
m
+1
¥
ô
Ú
,
P
•
φ
(
v
2
m
+1
) =
B
2
m
+1
"
í
Ø
1
b
a
,
k
´
ê
§
-
=
2
k
−
1
,
if
k
isodd
2
k
,
if
k
iseven.
X
J
P
k
= (
v
0
,v
1
,...,v
k
)
´
˜
^
•
•
k
´
§
¿
…
H
=(
L,H
)
´
G
˜
‡
(2
a
+
a
) -
-
CX
"
´
P
k
þ
Ä
—
ü
:
L
•
•
a
§
P
•
|
L
(
v
0
)
|
=
|
L
(
v
k
)
|
=
a
§
é
u
Ù
¦
:
L
•
•
2
a
+
a
§
P
•
|
L
(
v
i
)
|
= 2
a
+
a
( 1
≤
i
≤
k
−
1 )
"
@
o
•
3
´
P
k
þ
˜
‡
(
H
,a
)-
/Ú
φ
"
y
²
·
‚
r
ù
‡
y
²
©
•
ü
«
œ
¹
µ
œ
¹
1
k
= 2
m
•
ó
ê
Ï
L
Ú
n
1
Œ
§
•
3
L
L
(
v
k
−
1
)
þ
•
•
(
a
+
a
)
f
8
T
k
−
1
§
¦
é
u
L
(
v
k
−
1
)
þ
÷
v
|
B
k
−
1
∩
T
k
−
1
|≥
(1
−
(
m
−
1)
)
a
?
¿
a
-
f
8
B
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
"
Ï
•
ta
=
a
§
·
‚
k
|
T
k
−
1
−
L
(
v
k
)
|≥
a
= (1
−
(
m
−
1)
)
a
"
Ï
d
3
L
(
v
k
−
1
)
−
L
(
v
k
)
þ
•
3
a
-
f
8
B
k
−
1
§
•
¹
T
k
−
1
¥–
(1
−
(
m
−
1)
)
a
‡
ô
Ú
"
d
Ú
n
1
Œ
§
´
P
k
−
1
•
3
˜
‡
(
H
,a
) -
/Ú
φ
…
÷
v
φ
(
v
k
) =
L
(
v
k
)
"
œ
¹
2
k
= 2
m
+1
•
Û
ê
-
B
´
L
(
v
k
−
1
)
−
L
(
v
k
)
a
-
f
8
"
é
u
1
≤
i
≤
k
−
2
§
-
L
0
(
v
i
)=
L
(
v
i
)
§
¿
…
-
DOI:10.12677/aam.2021.1062342253
A^
ê
Æ
?
Ð
§
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
"
y
3
φ
Œ
±
ò
ÿ
´
P
k
þ
˜
‡
(
H
,a
)-
/Ú
§
…
¦
:
v
k
/
8
Ü
B
k
¥
ô
Ú
§
P
•
φ
(
v
k
) =
L
(
v
k
)
"
Ú
n
2
[7]
X
J
(
G
;
x,y
)
´
˜
‡
Œ
•
–
•
t
G
¿
é
ã
§
…
k
=
d
t/
2
e
,
K
G
‡
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
"
X
J
G
=
C
§
Ï
•
C
k
Œ
•
–
•
t
§
@
o
ù
‡
(
Ø
´
é
"
‡
ƒ
§
(
G
1
;
x
1
,y
1
)
Ú
(
G
2
;
x
2
,y
2
)
Ï
L
˜
X
G
¿
é
E
(
G
;
x,y
)
"
X
J
(
G
1
;
x
1
,y
1
)
Ú
(
G
2
;
x
2
,y
2
)
Ù
¥
˜
‡
•
¹
˜
‡
§
@
o
G
1
½
G
2
•
¹
˜
^
÷
v
‡
¦
´
"
‡
ƒ
§
Ï
•
G
•
¹
˜
‡
§
(
G
;
x,y
)
Œ
d
(
G
1
;
x
1
,y
1
)
Ú
(
G
2
;
x
2
,y
2
)
¿
é
"
é
u
i
=1
,
2 ,
G
i
´
˜
^
´
ë
x
i
Ú
y
i
"
@
o
G
´
˜
‡
§
¿
…
ù
‡
(
Ø
¤
á
"
½
n
2
b
q
,
a
´
˜
‡
ê
§
é
u
?
¿
Œ
•
–
•
t
G
¿
é
ã
G
§
t
∈{
4
q
−
1
,
4
q,
4
q
+1
,
4
q
+2
}
ž
§
G
´
((2+
1
q
)
a,a
)-DP-
/Ú
"
y
²
b
H
= (
L,H
)
´
G
((2+
1
q
)
a
)-
-
CX
"
·
‚
I
‡
`
²
G
k
˜
‡
(
H
,a
)-
/Ú
"
ù
‡
y
²
Ï
L
é
G
¥
:
ê
8
?
1
8
B
"
X
J
G
´
˜
^
´
§
@
o
G
´
(2
a,a
)-DP-
Œ
/
§
¿
…
(
Ø
"
b
G
Ø
´
˜
^
´
"
Ï
L
Ú
n
2
§
G
k
˜
^
•
•
k
´
P
= (
v
0
,v
1
,...,v
k
)(
t
∈{
4
q
−
1
,
4
q
}
ž
§
@
o
k
=2
q
;
t
∈{
4
q
+ 1
,
4
q
+2
}
,
@
o
k
=2
q
+ 1)
§
¦
G
¥
¤
k
:
v
1
,v
2
,...,v
k
−
1
Ý
•
2.
-
G
0
=
G
−{
v
1
,v
2
,...,v
k
−
1
}
"
@
o
G
0
´
˜
‡
Œ
•
–
•
4
q
−
1
G
¿
é
ã
§
½
ö
G
0
´
˜
^
´
"
b
G
0
´
˜
‡
Œ
•
–
•
4
q
−
1
G
¿
é
ã
§
@
o
Ï
L8
B
b
§
G
0
k
˜
‡
(
H
,a
)-
/Ú
φ
"
X
J
G
0
´
˜
^
´
§
Ï
•
´
´
(2
a,a
)-DP-
/Ú
§
@
o
G
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
)
þ
:
÷
v
L
0
(
v
l
) =
φ
(
v
l
)
¿
…
é
u
1
≤
i
≤
l
−
1
§
L
0
(
v
i
) =
L
(
v
i
)
"
Ï
L
í
Ø
1
§
P
k
˜
‡
(
H
,a
) -
/Ú
φ
"
@
o
φ
Ú
ψ
Ü
å
5
Ò
´
ã
G
˜
‡
(
H
,a
)-
/Ú
"
Ï
L
½
n
2
§
é
u
t
∈{
4
q
−
1
,
4
q,
4
q
+1
,
4
q
+2
}
§
Q
t
©
ê
DP
-
Ú
ê´
–
õ
2 +
1
q
"
•
`
²
ù
‡
ª
¤
á
§
·
‚
I
‡
E
§
é
u
z
‡
ê
a
§
˜
‡
ã
á
u
Q
t
§
§
Ø
´
((2+
1
q
)
a
−
1
,a
)
-DP-
/Ú
"
Ú
n
3
b
a
,
k
´
˜
‡
ê
¿
…
b
´
˜
‡
¢ê
§
¦
a
´
˜
‡
ê
…
<
2
k
−
1
,
if
k
isodd
2
k
,
if
k
iseven.
-
P
k
= (
v
0
,v
1
,...,v
k
)
´
˜
^
´
.
-
X
1
,
X
2
´
a
-
8
Ü
.
@
o
´
P
k
•
3
˜
‡CX
H
= (
L,H
)
…
±
e
^
‡
Ñ
‡
÷
v
µ
•
L
(
v
0
) =
X
1
§
L
(
v
l
) =
X
2
•|
L
(
v
i
)
|
= 2
a
+
a
(1
≤
i
≤
k
−
1)
•
´
P
k
Ø
´
(
H
,a
)-
/Ú
y
²
-
M
f
(
f
=1
,
3
,
5
,...,
2
q
−
3),
N
g
(
g
=2
,
4
,
6
,...,
2
q
−
2),
Z
h
(
h
=1
,
3
,
5
,...,
2
q
−
1)
´
Ø
ƒ
ô
Ú
8
§
…
|
M
f
|
=
|
N
g
|
=
a
,
|
Z
h
|
=
a
.
-
H
= (
L,H
)
´
´
P
k
þ
˜
‡CX
§
½
Â
X
e
DOI:10.12677/aam.2021.1062342254
A^
ê
Æ
?
Ð
§
JJ
•
L
(
v
0
) =
X
1
,
L
(
v
l
) =
X
2
,
L
(
v
1
) =
X
1
∪
M
1
∪
Z
1
.
•|
L
(
v
2
i
+1
)
|
=
N
2
i
∪
M
2
i
+1
∪
Z
2
i
+1
,
i
= 1
,
2
,
3
,...,q
−
2.
•|
L
(
v
2
j
)
|
=
N
2
j
∪
M
2
j
−
1
∪
Z
2
j
−
1
,
j
= 1
,
2
,
3
,...,q
−
1.
•
X
J
k
= 2
q
,
@
o
L
(
v
2
q
−
1
) =
X
2
∪
N
2
q
−
2
∪
Z
2
q
−
1
;
X
J
k
= 2
q
+1,
@
o
L
(
v
2
q
) =
X
2
∪
M
2
q
−
1
∪
Z
2
q
−
1
.
·
‚
A
T
‡
y
²
P
k
Ø
´
(
H
,a
)-
/Ú
ä
ó
1
é
u
?
¿
j
∈{
2
,
3
,
4
,...,q
}
§
X
J
φ
´
´
P
2
j
−
2
þ
˜
‡
(
H
,a
)-
/Ú
§
@
o
|
φ
(
v
2
j
−
2
)
∩
N
2
j
−
2
|≥
a
−
(
j
−
1)
a
"
y
²
·
‚
e
5
é
e
I
j
?
1
8
B
b
§
?
¤
ù
‡
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
¿
…
ù
‡
ä
ó
é
u
j
0
<j
¤
á
"
φ
´
´
P
2
j
−
2
þ
˜
‡
(
H
,a
)-
/Ú
"
é
´
P
2
j
−
4
þ
/Ú
φ
•
›
A^
8
B
b
§
·
‚
Œ
±
|
φ
(
v
2
j
−
4
)
∩
N
2
j
−
4
|≥
a
−
(
j
−
2)
a
K
|
φ
(
v
2
j
−
3
)
∩
N
2
j
−
4
|≤
(
j
−
2)
a
"
d
d
Œ
í
|
φ
(
v
2
j
−
3
)
∩
(
M
2
j
−
3
∪
Z
2
j
−
3
)
|≥
a
−
(
j
−
2)
a
Ï
d
|
φ
(
v
2
j
−
2
)
∩
(
M
2
j
−
3
∪
Z
2
j
−
3
)
|≤
(
j
−
1)
a
l
|
φ
(
v
2
j
−
2
)
∩
N
2
j
−
2
|≥
a
−
(
j
−
1)
a
b
k
=2
q
´
˜
‡
ó
ê
§
¿
…
´
φ
´
´
P
2
q
˜
‡
(
H
,a
) -
/Ú
"
@
o
|
φ
(
v
2
q
−
2
)
∩
N
2
q
−
2
|≥
a
−
(
q
−
1)
a
"
Ï
•
φ
(
v
2
q
)=
X
2
§
·
‚
Œ
±
φ
(
v
2
q
−
1
)
⊆
(
N
2
q
−
2
−
φ
(
v
2
q
−
2
))
∪
Z
2
q
−
1
"
´
|
(
N
2
q
−
2
−
φ
(
v
2
q
−
2
))
∪
Z
2
q
−
1
|≤
(
q
−
1)
a
+
a
=
qa<a
§
K
:
v
2
q
−
1
Œ
/
a
‡
ô
Ú
†
:
v
2
q
−
2
/
ô
Ú
7
½
ƒ
§
g
ñ
"
b
k
= 2
q
+1
´
˜
‡
Û
ê
§
…
φ
´
´
P
2
q
+1
˜
‡
(
H
,a
)-
/Ú
"
d
ä
ó
1
Œ
•
§
|
φ
(
v
2
q
−
2
)
∩
N
2
q
−
2
|≥
a
−
(
q
−
1)
a
"
Ï
d
|
φ
(
v
2
q
−
1
)
∩
N
2
q
−
2
|≤
(
q
−
1)
a
"
Ï
•
φ
(
v
2
q
+1
) =
X
2
"
¤
±
φ
(
v
2
q
)
⊆
(
M
2
q
−
1
∪
Z
2
q
−
1
)
−
φ
(
v
2
q
−
1
)
"
´
|
(
M
2
q
−
1
∪
Z
2
q
−
1
)
−
φ
(
v
2
q
−
1
)
|≤
a
+
a
−
(
a
−
(
q
−
1)
a
) =
qa<a
"
d
d
·
‚
:
v
2
q
Œ
/
a
‡
ô
Ú
†
:
v
2
q
−
1
/
ô
Ú
7
½
ƒ
§
g
ñ
"
½
n
3
b
q
§
a
´
˜
‡
ê
§
¿
…
b
´
˜
‡
¢ê
§
¦
a
´
˜
‡
ê
§
…
<
1
q
"
é
u
k
∈{
4
q
−
1
,
4
q,
4
q
+1
,
4
q
+2
}
§
@
o
•
3
˜
‡
ã
G
∈Q
t
,
¦
G
Ø
´
((2+
)
a,a
-
/Ú
"
y
²
-
p
=
(2+
)
a
a
2
"
-
G
d
Œ
•
•
t
2
´
¿
E
§
ü
‡
à:
P
•
x
Ú
y
§
@
o
G
∈Q
t
"
·
‚
A
T
y
²
G
Ø
´
((2 +
)
a,a
)-
/Ú
"
-
X
Ú
Y
´
¹
k
(2
a
+
a
)
ƒ
8
Ü
§
¿
…
-
L
(
x
) =
X
and
L
(
y
)=
Y
"
@
o
Ò
k
p
«
(
H
,a
)-
/Ú
•
ª
"
z
«
/Ú
φ
Ñé
A
˜
^
Œ
•
•
t
2
´
"
3
z
^
´
§
½
Â
(
H
,a
)
Ó
Ú
n
3
CX
§
X
1
^
φ
(
x
)
O
“
§
Y
1
^
φ
(
y
)
O
“
"
@
o
d
Ú
n
3
Œ
DOI:10.12677/aam.2021.1062342255
A^
ê
Æ
?
Ð
§
JJ
§
3
x
Ú
y
þ
(
H
,a
) -
/Ú
Ø
Œ
±
ò
ÿ
‡
ã
G
/Ú
"
Ï
L
½
n
3
§
é
u
k
∈{
4
q
−
1
,
4
q,
4
q
+1
,
4
q
+2
}
§
ã
a
Q
t
©
ê
DP-
/Ú
ê
–
´
2+
1
q
"
(
Ü
½
n
2
§
K
¤
½
n
1
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(2
m
,
m
)-Choosable.
Journalof
GraphTheory
,
22
,245-252.
https://doi.org/10.1002/(SICI)1097-0118(199607)22:3
h
245::AID-JGT5
i
3.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ˇr
S
k, 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.1062342256
A^
ê
Æ
?
Ð