设为首页
加入收藏
期刊导航
网站地图
首页
期刊
数学与物理
地球与环境
信息通讯
经济与管理
生命科学
工程技术
医药卫生
人文社科
化学与材料
会议
合作
新闻
我们
招聘
千人智库
我要投稿
办刊
期刊菜单
●领域
●编委
●投稿须知
●最新文章
●检索
●投稿
文章导航
●Abstract
●Full-Text PDF
●Full-Text HTML
●Full-Text ePUB
●Linked References
●How to Cite this Article
AdvancesinAppliedMathematics
A^
ê
Æ
?
Ð
,2021,10(8),2660-2672
PublishedOnlineAugust2021inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2021.108276
²
¡
ã
Ã
>
/Ú
___
jjj
§§§
ÁÁÁ
öööIII
∗
ú
ô
“
‰
Œ
Æ
ê
Æ
†
O
Ž
Å
‰
ÆÆ
§
ú
ô
7
u
Â
v
F
Ï
µ
2021
c
7
2
F
¶
¹
^
F
Ï
µ
2021
c
7
21
F
¶
u
Ù
F
Ï
µ
2021
c
8
4
F
Á
‡
é
u
ã
G
˜
‡
>
/Ú
c
:
E
(
G
)
→{
1
,
2
,...,k
}
§
e
÷
v
?
¿
ü
^
ƒ
>
Ñ
/
Ø
Ó
ô
Ú
§
…
ã
G
Ø
•
3
V
Ú
§
K
c
¡
•
ã
G
˜
‡
Ã
k
-
>
/Ú
"
ã
G
Ã
>
Ú
ê
•
¦
ã
G
k
˜
‡
Ã
k
-
>
/Ú
•
ê
k
§
^
χ
0
a
(
G
)
L
«
"
©
Ì
‡
y
²
e
ã
G
´
Ø
¹
ƒ
i
-
§
…
5
-
§
j
-
Ø
²
¡
ã
§
i
∈{
3
,
4
}
,j
∈{
4
,
6
}
§
K
χ
0
a
(
G
)
≤
∆(
G
)+2
"
'
…
c
Ã
>
/Ú
§
²
¡
ã
§
AcyclicEdgeColoringofPlanar
Graphs
QiJia,HongguoZhu
∗
CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang
Received:Jul.2
nd
,2021;accepted:Jul.21
st
,2021;published:Aug.4
th
,2021
∗
Ï
Õ
Š
ö
"
©
Ù
Ú
^
:
_
j
,
Á
öI
.
²
¡
ã
Ã
>
/Ú
[J].
A^
ê
Æ
?
Ð
,2021,10(8):2660-2672.
DOI:10.12677/aam.2021.108276
_
j
§
Á
öI
Abstract
Aproperedge
k
-coloringisamapping
c
:
E
(
G
)
→{
1
,
2
,...,k
}
suchthatanytwoadjacent
edgesreceivedifferentcolors. Aproperedge
k
-coloring
c
of
G
iscalledacyclicifthere
arenobichromaticcyclesin
G
.Theacyclicchromaticindexof
G
, denotedby
χ
0
a
(
G
)
,
isthesmallestinteger
k
suchthat
G
isacyclicallyedge
k
-colorable. Inthispaper, we
showthatif
G
isaplanargraphcontainingnoadjacent
i
-cyclesandwithouta5-cycle
adjacenttoa
j
-cycle,
i
∈{
3
,
4
}
,j
∈{
4
,
6
}
,then
χ
0
a
(
G
)
≤
∆(
G
)+2
.
Keywords
AcyclicEdgeColoring,PlaneGraph,Cycle
Copyright
c
2021byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.
Ú
ó
©
•
Ä
k
•
{
ü
ã
.
é
u
˜
‡
ã
G
,
r
§
º:
8
!
>
8
!
¡
8
!
•
Œ
Ý
!
•
Ý
9
Œ
•
©
O
P
Š
V
(
G
)
,E
(
G
)
,F
(
G
),∆(
G
) (
{P
•
∆),
δ
(
G
),
9
g
(
G
),
é
u
²
¡
ã
G
˜
‡
¡
f
,
e
d
(
f
)=
k
(
½
d
(
f
)
≥
k
,
½
d
(
f
)
≤
k
),
K
¡
f
•
˜
‡
k
-
¡
(
½
k
+
-
¡
,
½
k
−
-
¡
).
é
u
²
¡
ã
G
˜
‡
º:
v
,
e
d
(
v
)=
k
(
½
d
(
v
)
≥
k
,
½
d
(
v
)
≤
k
),
K
¡
v
•
˜
‡
k
-
:
(
½
k
+
-
:
,
½
k
−
-
:
).
ã
G
Ã
k
-
>
/Ú
´
•
N
c
:
E
(
G
)
→{
1
,
2
,...,k
}
,
÷
v
é
?
¿
ü
^
ƒ
>
x
,
y
,
k
c
(
x
)
6
=
c
(
y
),
…
ã
G
Ø
•
3
V
Ú
,
ã
G
Ã
>
Ú
ê
•
¦
ã
G
k
˜
‡
Ã
k
-
>
/Ú
•
ê
k
,
^
χ
0
a
(
G
)
L
«
.
Fiam
ˇ
cik
J
Ñ
˜
‡
'
u
²
¡
ã
Ã
>
/Ú
Í
¶
ß
Ž
.
ß
Ž
1
[1]
é
u
?
¿
²
¡
ã
G
,
k
χ
0
a
(
G
)
≤
∆(
G
)+2.
ù
‡
ß
Ž
–
8
„
v
k
)û
.1991
c
Alon
,
McDiarmid
Ú
Reed
[2]
y
²
é
²
¡
ã
G
,
k
χ
0
a
(
G
)
≤
64∆;1998
c
Molloy
Ú
Reed
[3]
y
²
é
²
¡
ã
G
,
k
χ
0
a
(
G
)
≤
16∆;2020
c
Fialho
[4]
<
y
²
é
²
¡
ã
G
,
k
χ
0
a
(
G
)
≤
3
.
569(∆
−
1).
é
u
g
(
G
)
≥
4
²
¡
ã
G
,
Ó
|
,
‘
…
Ú
²
x
[5]
y
²
χ
0
a
(
G
)
≤
∆(
G
)+2;
é
u
g
(
G
)
≥
5
²
¡
ã
G
,
û
ï
¹
[6]
<
y
²
χ
0
a
(
G
)
≤
∆(
G
) + 1;
Ó
c
,
û
ï
¹
[6]
<
y
²
e
•
Œ
Ý
÷
v
DOI:10.12677/aam.2021.1082762661
A^
ê
Æ
?
Ð
_
j
§
Á
öI
∆(
G
)
≥
9,
K
χ
0
a
(
G
)=∆(
G
);
é
u
g
(
G
)
≥
6
²
¡
ã
G
,
Hud
´
ak
[7]
<
y
²
e
•
Œ
Ý
÷
v
∆(
G
)
≥
6,
K
χ
0
a
(
G
) =∆(
G
);
é
u
g
(
G
)
≥
7
²
¡
ã
G
,
‘
…
,
Ó
|
,
¸
Ú
²
[8]
y
²
e
•
Œ
Ý
÷
v
∆(
G
)
≥
5,
K
χ
0
a
(
G
) =∆(
G
);
é
u
g
(
G
)
≥
8
²
¡
ã
G
,
‘
…
,
Ó
|
,
¸
Ú
²
[8]
y
²
e
•
Œ
Ý
÷
v
∆(
G
)
≥
4,
K
χ
0
a
(
G
) = ∆(
G
).
é
u
Ø
¹
4-
²
¡
ã
G
,
A
c
Ú
•
²
[9]
y
²
χ
0
a
(
G
)
≤
∆(
G
)+3;
é
u
Ø
¹
4-
…
•
Œ
Ý
÷
v
∆(
G
)
≥
5
²
¡
ã
G
,
‘
…
,
Ó
|
Ú
²
x
[10]
y
²
χ
0
a
(
G
)
≤
∆(
G
)+2;
é
u
Ø
¹
5-
²
¡
ã
G
,
Ó
|
,
‘
…
Ú
²
x
[11]
y
²
χ
0
a
(
G
)
≤
∆(
G
)+2;
é
u
Ø
¹
4-,6-
²
¡
ã
G
,
û
ï
¹
,
4
?
ý
Ú
Ç
ï
û
[12]
y
²
χ
0
a
(
G
)
≤
∆(
G
)+2.
é
u
3-,3-
Ø
²
¡
ã
G
,
[13]
<
y
²
χ
0
a
(
G
)
≤
∆(
G
)+5;
é
u
3-,5-
Ø
²
¡
ã
G
,
²
x
Ú
Ó
|
[14]
y
²
χ
0
a
(
G
)
≤
∆(
G
)+2;
é
u
3-,6-
Ø
²
¡
ã
G
,
²
x
,
Ó
|
Ú
Ç
ï
û
[15]
<
y
²
χ
0
a
(
G
)
≤
∆(
G
)+2.
é
u
Ã
ƒ
n
/
²
¡
ã
G
,
Ó
|
[16]
<
y
²
χ
0
a
(
G
)
≤
∆(
G
)+2;
é
u
i
-,
j
-
Ø
ƒ
,
Ù
¥
i,j
∈{
3
,
4
}
²
¡
ã
G
,
AnnaFiedorowicz
[17]
y
²
χ
0
a
(
G
)
≤
∆(
G
)+2.
©
ò
y
²
e
¡
½
n
:
½
n
1
e
ã
G
´
Ø
¹
ƒ
i
-
,
…
5-,
j
-
Ø
²
¡
ã
,
i
∈{
3
,
4
}
,j
∈{
4
,
6
}
,
K
χ
0
a
(
G
)
≤
∆(
G
)+2.
2.
P
Ò
-
G
•
˜
‡
{
ü
²
¡
ã
,
é
u
?
¿
:
v
∈
V
(
G
),
^
N
(
v
)
L
«
†
v
ƒ
º:
8
Ü
,
k
d
(
v
)=
|
N
(
v
)
|
.
P
N
k
(
v
)=
{
x
∈
N
(
v
)
|
d
(
x
)=
k
}
,
…
n
k
(
v
)=
|
N
k
(
v
)
|
.
e
º:
v
÷
v
d
(
v
)=
k
,
…
v
†
u
ƒ
,
K
¡
v
•
u
k
-
:
.
é
u
¡
f
∈
F
(
G
),
^
M
(
v
)
L
«
†
v
ƒ
'
é
¡
8
Ü
,
P
M
k
(
v
)=
{
f
∈
M
(
v
)
|
d
(
f
)=
k
}
,
…
m
k
(
v
)=
|
M
k
(
v
)
|
.
^
b
(
f
)
L
«
¡
f
>
.
,
e
u
1
,u
2
,...,u
n
•
b
(
f
)
þ
U
^
S
ü
:
,
K
P
‰
f
= [
u
1
u
2
...u
n
],
δ
(
f
)
L
«
¡
f
•
Ý
,
Ù
Š
•
†
¡
f
ƒ
'
é
:
•
Ý
.
-
c
•
G
˜
‡
Û
Ü
Ã
>
/Ú
,
^
C
(
u
)
L
«
3
Ã
>
/Ú
c
¥
†
:
u
ƒ
'
é
>
¤
/
ô
Ú
8
Ü
,
•
B
å
„
,
^
[
k
]
L
«
{
1
,
2
,...,k
}
.
^
F
(
uv
)
L
«
>
uv
B
^
Ú
8
Ü
,
3
Ã
>
/Ú
c
¥
˜
^
(
α,β
)-
V
Ú
´
´
•
d
α,β
ù
ü
«
ô
Ú
O
X
Ú
>
¤
|
¤
´
,
e
(
α,β
)-
V
Ú
´
"
à
©
O
•
:
u
Ú
:
v
,
K
ò
ù
´
P
‰
(
α,β
)
(
u,v
)
-
V
Ú
´
.
3.
½
n
1
y
²
3.1.
4
‡
~
5
Ÿ
©
Ì
‡
Ï
L
=
£
•{
5
y
²
½
n
1.
ã
G
´
½
n
1
¥
¦
|
V
(
G
)
|
+
|
E
(
G
)
|
•
˜
‡
‡
~
.
=
ã
G
´
Ø
¹
ƒ
i
-
,
…
5
,j
-
Ø
,
i
∈{
3
,
4
}
,j
∈{
4
,
6
}
,
χ
0
a
(
G
)
≥
∆+3
²
¡
ã
.
G
´
ë
Ï
{
ü
²
¡
ã
.
-
L
=
{
1
,
2
,...,k
}
•
ô
Ú
8
,
Ù
¥
k
=∆(
G
)+2.
e
5
,
·
‚
&?
G
(
5
Ÿ
.
DOI:10.12677/aam.2021.1082762662
A^
ê
Æ
?
Ð
_
j
§
Á
öI
Ú
n
1
²
¡
ã
G
´
2-
ë
Ïã
.
y
²
b
v
•
²
¡
ã
G
˜
‡•
:
,
C
1
,C
2
,...,C
t
(
t
≥
2)
•
G
\
v
ë
Ï
Ü
©
.
é
u
1
≤
i
≤
t
,
G
i
=
C
i
∪{
v
}
þ
•
3
Ã
k
-
>
/Ú
c
i
.
Ï
L
N
c
i
¦
†
v
'
é
>
/
Ø
Ó
ô
Ú
,
ù
ž
k
‡
ô
Ú
Œ
±
ò
ã
G
/
Ð
,
g
ñ
.
Ú
n
2
G
¥
2-
:
Ø
†
3
−
-
:
ƒ
.
y
²
-
v
•
˜
‡
2-
:
,
u
´
†
v
ƒ
3
−
-
:
,
•
?
Ø
d
(
u
) = 3
œ
¹
,
d
(
u
) = 2
œ
¹
Ó
n
Œ
.
P
N
(
v
) =
{
u,w
}
,
N
(
u
) =
{
v,u
1
,u
2
}
.
-
G
0
=
G
−
uv
,
G
0
k
˜
‡
Ã
k
-
>
/Ú
c
.
•
Ä
e
¡
ü
«
œ
¹
:
(1)
c
(
vw
)
/
∈{
c
(
uu
1
)
,c
(
uu
2
)
}
d
ž
Œ
±
^
L
\{
c
(
vw
)
,c
(
uu
1
)
,c
(
uu
2
)
}
¥
ô
Ú/
>
vu
,
g
ñ
.
(2)
c
(
vw
)
∈{
c
(
uu
1
)
,c
(
uu
2
)
}
>
uv
B
^
Ú
F
(
uv
)
÷
v
:
|
F
(
uv
)
|≤|
C
(
u
)
∪
C
(
v
)
∪
C
(
w
)
|≤
d
(
u
)
−
1+
d
(
v
)
−
2+
d
(
w
)
−
1
≤
∆+1
<k
,
Œ
-
α
∈
L
\
F
(
uv
)
,c
(
uv
) =
α
,
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
Ú
n
3
v
•
ã
G
˜
‡
4
+
-
:
,
e
n
2
(
v
) = 1,
K
n
2
(
v
)+
n
3
(
v
)
≤
d
−
3.
y
²
b
n
2
(
v
) +
n
3
(
v
)
≥
d
−
2.
P
N
(
v
)=
{
v
1
,v
2
,...,v
d
}
,
d
(
v
1
)=2,
d
(
v
i
)
≤
3
,i
=
2
,
3
,...,d
−
2.
•
?
Ø
d
(
v
i
)=3,
i
=2
,
3
,...,d
−
2
œ
¹
,
Ù
¦
œ
¹
Ó
n
Œ
.
-
N
(
v
1
)=
{
v,v
0
1
}
,
N
(
v
i
)=
{
v,v
0
i
,v
00
i
}
,
i
∈{
2
,
3
,...,d
−
2
}
,
G
0
=
G
−
vv
1
,
G
0
k
˜
‡
Ã
k
-
>
/Ú
c
.
-
c
(
vv
i
)=
i
,
i
∈{
2
,
3
,...,d
}
.
•
Ä
e
¡
n
«
œ
¹
:
œ
¹
1
c
(
v
1
v
0
1
)
/
∈{
2
,
3
,...,d
}
d
ž
Œ
-
α
∈
L
\{
2
,
3
,...,d,c
(
v
1
v
0
1
)
}
,c
(
vv
1
) =
α
,
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
œ
¹
2
c
(
v
1
v
0
1
)
∈{
2
,
3
,...,d
−
2
}
Ø
”
˜
„
5
,
-
c
(
v
1
v
0
1
) = 2.
>
vv
1
B
^
Ú
F
(
vv
1
)
÷
v
:
|
F
(
vv
1
)
|≤|{
2
,
3
,...,d,c
(
v
2
v
0
2
)
,c
(
v
2
v
00
2
)
}|≤
d
−
1+2=
d
+1
<k
.
k
«
ô
Ú
Œ
ò
ã
G
/
Ð
,
g
ñ
.
œ
¹
3
c
(
v
1
v
0
1
)
∈{
d
−
1
,d
}
Ø
”
˜
„
5
,
-
c
(
v
1
v
0
1
) =
d
.
²
L
v
0
1
,v
d
˜
½
•
3
˜
^
(
d,α
)
(
v
1
,v
)
-
V
Ú
´
,
α
∈{
1
,d
+1
,d
+2
}
,
Ä
K
Œ
±
^
α
/
>
vv
1
,
¦
k
«
ô
Ú
ò
ã
G
/
Ð
,
)
g
ñ
.
{
1
,d,d
+1
,d
+2
}⊆
C
(
v
0
1
),
•
3
ô
Ú
i
0
,2
≤
i
0
≤
d
−
2,
…
i
0
/
∈
C
(
v
0
1
),
^
i
0
-
/
>
v
1
v
0
1
,
†
œ
¹
2
a
q
,
G
k
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
Ú
n
4
v
•
ã
G
˜
‡
d
-
:
,
u
•
v
2-
:
,
e
u
†
3-
¡
'
é
,
K
d
≥
5,
…
n
2
(
v
)+
n
3
(
v
)
≤
d
−
4.
y
²
Ä
k
y
²
d
≥
5.
d
= 4,
P
N
(
v
) =
{
u,v
1
,v
2
,v
3
}
,N
(
u
) =
{
v,v
1
}
.
-
G
0
=
G
−
vu
,
G
0
k
˜
‡
Ã
k
-
>
/Ú
c
.
DOI:10.12677/aam.2021.1082762663
A^
ê
Æ
?
Ð
_
j
§
Á
öI
d
Ú
n
2,
d
(
v
1
)
≥
4,
-
c
(
vv
i
) =
i
,
i
∈{
1
,
2
,
3
}
.
•
Ä
e
¡
ü
«
œ
¹
:
œ
¹
1
c
(
v
1
u
)
/
∈{
2
,
3
}
>
uv
B
^
Ú
F
(
uv
)
÷
v
:
|
F
(
uv
)
|≤|
C
(
u
)
∪
C
(
v
)
|≤
d
(
u
)
−
1+
d
(
v
)
−
1 = 4
<k
,
d
ž
Œ
-
α
∈
L
\
F
(
uv
)
,c
(
uv
) =
α
,
Ï
d
k
«
ô
Ú
Œ
ò
ã
G
/
Ð
,
g
ñ
.
œ
¹
2
c
(
v
1
u
)
∈{
2
,
3
}
>
uv
B
^
Ú
F
(
uv
)
÷
v
:
|
F
(
uv
)
|≤|
C
(
u
)
∪
C
(
v
)
∪
C
(
v
1
)
|≤
d
(
u
)
−
1+
d
(
v
)
−
2+
d
(
v
1
)
−
2 =
d
(
v
1
)+1
<k
,
d
ž
Œ
-
α
∈
L
\
F
(
uv
)
,c
(
uv
) =
α
,
Ï
d
k
«
ô
Ú
Œ
ò
ã
G
/
Ð
,
g
ñ
.
y
3
y
²
n
2
(
v
)+
n
3
(
v
)
≤
d
−
4.
n
2
(
v
)+
n
3
(
v
)
≥
d
−
3.
P
N
(
v
) =
{
u,v
1
,v
2
,...,v
d
−
1
}
,N
(
u
) =
{
v,v
1
}
.
•
I
?
Ø
d
(
v
i
) = 3,
i
=2
,
3
,...,d
−
3
œ
¹
,
Ù
¦
œ
¹
Ó
n
Œ
,
-
N
(
v
i
)=
{
v,v
0
i
,v
00
i
}
,
G
0
=
G
−
uv
,
G
0
k
˜
‡
Ã
k
-
>
/Ú
c
.
Ø
”
˜
„
5
,
-
c
(
vv
i
) =
i,i
= 1
,
2
,...,d
−
1.
•
Ä
e
¡
n
«
œ
¹
:
œ
¹
1
c
(
uv
1
)
/
∈{
2
,...,d
−
1
}
>
uv
B
^
Ú
F
(
uv
)
÷
v
:
|
F
(
uv
)
|≤|
C
(
u
)
∪
C
(
v
)
|≤
d
(
u
)
−
1+
d
(
v
)
−
1 =
d<k
,
Ï
d
k
«
ô
Ú
Œ
ò
ã
G
/
Ð
,
g
ñ
.
œ
¹
2
c
(
uv
1
)
∈{
2
,
3
,...,d
−
3
}
Ø
”
˜
„
5
,
c
(
uv
1
)=2.
>
uv
B
^
Ú
F
(
uv
)
÷
v
:
|
F
(
uv
)
|≤|
C
(
u
)
∪
C
(
v
)
∪
C
(
v
2
)
|≤
d
(
u
)
−
1+
d
(
v
)
−
2+
d
(
v
2
)
−
1 = 1+
d
−
2+2 =
d
−
1
<k
,
Ï
d
k
«
ô
Ú
Œ
ò
ã
G
/
Ð
,
g
ñ
.
œ
¹
3
c
(
uv
1
)
∈{
d
−
2
,d
−
1
}
Ø
”
˜
„
5
,
c
(
uv
1
)=
d
−
1.
K
•
3
˜
^
²
L
v
1
,v
d
−
1
(
d
−
1
,α
)
(
u,v
)
-
´
,
Ä
K
,
Œ
-
c
(
uv
)
∈
L
\{
1
,
2
,...,d
−
1
}
,
c
=
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
e
α
∈{
2
,...,d
−
1
}
,
K
Œ
-
c
(
uv
)
∈{
d,d
+ 1
,d
+ 2
}
,
l
k
«
ô
Ú
Œ
ò
ã
G
/
Ð
,
g
ñ
.
α
∈{
d,d
+ 1
,d
+ 2
}
.
y
Œ
ä½
{
d,d
+1
,d
+2
}⊆
C
(
v
1
),
Ä
K
Œ
-
c
(
uv
)
∈{
d,d
+1
,d
+2
}\
C
(
v
1
),
c
=
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
K
•
3
i
0
,
2
≤
i
0
≤
d
−
3,
…
i
0
/
∈
C
(
v
1
),
d
ž
Œ
^
i
0
-
/
>
uv
1
,
†
œ
¹
2
a
q
,
G
k
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
Ú
n
5[18]
é
u
?
¿
>
uv
∈
E
(
G
),
k
d
(
u
)+
d
(
v
)
≥
7.
Ú
n
6
-
f
•
˜
‡
3-
¡
,
P
‰
f
= [
uvw
].
e
d
(
v
) = 3,
K
d
(
u
)
,d
(
w
)
≥
5.
y
²
d
Ú
n
5,
e
d
(
v
) = 3,
K
d
(
u
)
≥
4
,d
(
w
)
≥
4.
-
d
(
u
) = 4
,N
(
u
) =
{
v,w,u
1
,u
2
}
,N
(
v
) =
{
u,w,v
1
}
.
du
G
Ø
¹
ƒ
n
/
,
u
1
,u
2
,v
1
þ
Ø
ƒ
Ó
.
-
G
0
=
G
−
uv
,
G
0
k
˜
‡
Ã
k
-
>
/
Ú
c
.
b
c
(
uu
1
) = 1
,c
(
uu
2
) = 2
,c
(
uw
) = 3.
•
Ä
e
¡
n
«
œ
¹
:
œ
¹
1
|
C
(
u
)
∩
C
(
v
)
|
= 0
>
uv
B
^
Ú
F
(
uv
)
÷
v
:
|
F
(
uv
)
|≤|
C
(
u
)
∪
C
(
v
)
|≤
d
(
u
)
−
1+
d
(
v
)
−
1= 3 +2=5
<k
,
d
ž
k
«
ô
Ú
Œ
ò
ã
G
/
Ð
,
g
ñ
.
DOI:10.12677/aam.2021.1082762664
A^
ê
Æ
?
Ð
_
j
§
Á
öI
œ
¹
2
|
C
(
u
)
∩
C
(
v
)
|
= 1
(1)
c
(
vv
1
)
∈{
c
(
uu
1
)
,c
(
uu
2
)
}
.
-
c
(
vv
1
) = 1
,c
(
vw
) = 4.
²
L
v
1
,u
1
˜
½
•
3
∆
−
2
^
(1
,α
)
(
u,v
)
-
V
Ú
´
,
α
∈{
5
,...,k
}
.
e
•
3
γ
∈{
5
,...,k
}
,
…
²
L
v
1
,u
1
Ã
(1
,γ
)
(
u,v
)
-
V
Ú
´
,
K
Œ
-
c
(
uv
)=
γ
,
c
=
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
{
1
,
5
,...,k
}⊆
C
(
v
1
).
e
3
/
∈
C
(
v
1
),
K
Œ
^
3
-
/
>
vv
1
,
d
ž
²
L
v
1
,w
˜
½
•
3
∆
−
2
^
(3
,β
)
(
u,v
)
-
V
Ú
´
,
β
∈{
5
,...,k
}
.
e
•
3
γ
∈{
5
,...,k
}
,
…
²
L
v
1
,w
Ã
(3
,γ
)
(
u,v
)
-
V
Ú
´
,
K
Œ
-
c
(
uv
) =
γ
,
c
=
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
C
(
w
) =
{
3
,
4
,
5
,...,k
}
.
d
ž
Œ
^
3
/
>
vv
1
,4
/
>
uw
,1
/
>
vw
,
β
/
>
uv
,
c
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
d
þ
ã
?
Ø
Œ
3
∈
C
(
v
1
),
=
C
(
v
1
) =
{
1
,
3
,
5
,...,k
}
.
d
ž
Œ
^
4
-
/
>
vv
1
,
^
1
-
/
>
vw
,
^
α
/
>
uv
,
α
∈
L
\{
1
,
2
,
3
,
4
}
,
c
=
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
(2)
c
(
vv
1
) =
c
(
uw
)
,c
(
vw
) = 4.
²
L
v
1
,w
˜
½
•
3
∆
−
2
^
(3
,β
)
(
u,v
)
-
V
Ú
´
,
β
∈{
5
,...,k
}
.
e
•
3
γ
∈{
5
,...,k
}
,
…
²
L
v
1
,w
Ã
(3
,γ
)
(
u,v
)
-
V
Ú
´
,
K
Œ
-
c
(
uv
)=
γ
,
c
=
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
C
(
w
)=
{
3
,
4
,
5
,...,k
}
,
{
3
,
5
,...,k
}⊆
C
(
v
1
).
d
ž
Œ
^
{
1
,
2
}\
C
(
v
1
)
¥
ô
Ú
-
/
>
vv
1
,
¦
c
(
vv
1
)
∈{
c
(
uu
1
)
,c
(
uu
2
)
}
,
†
(1)
?
Ø
a
q
,
c
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
(3)
c
(
vw
)
∈{
c
(
uu
1
)
,c
(
uu
2
)
}
.
-
c
(
vw
)=
c
(
uu
1
)=1
,c
(
vv
1
)=4.
²
L
w,u
1
˜
½
•
3
∆
−
2
^
(1
,α
)
(
u,v
)
-
V
Ú
´
,
α
∈
{
5
,...,k
}
.
e
•
3
γ
∈{
5
,...,k
}
,
…
²
L
w,u
1
Ã
(1
,γ
)
(
u,v
)
-
V
Ú
´
,
K
Œ
-
c
(
uv
) =
γ
,
c
=
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
C
(
w
) =
{
1
,
3
,
5
,...,k
}
.
{
5
,...,k
}⊆
C
(
v
1
),
Ä
K
Œ
^
4
/
>
uv
,
^
{
5
,...,k
}\
C
(
v
1
)
-
/
>
vv
1
,
)
g
ñ
.
d
ž
Ï
L
^
{
1
,
3
}\
C
(
v
1
)
/
>
vv
1
,
^
4
/
>
vw
,
†
(1)(2)
?
Ø
a
q
,
c
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
œ
¹
3
|
C
(
u
)
∩
C
(
v
)
|
= 2
(1)
c
(
vv
1
) = 3
,c
(
vw
) = 1.
²
L
u
1
,w
˜
½
•
3
∆
−
1
^
(1
,α
)
(
u,v
)
-
V
Ú
´
,
α
∈{
4
,...,k
}
.
e
•
3
γ
∈{
4
,...,k
}
,
…
²
L
u
1
,w
Ã
(1
,γ
)
(
u,v
)
-
V
Ú
´
,
K
Œ
-
c
(
uv
)=
γ
,
c
=
•
G
˜
‡
Ã
k
-
>
/Ú
,
g
ñ
.
C
(
w
) =
{
1
,
3
,
4
,...,k
}
,d
(
w
) = ∆+1,
g
ñ
.
(2)
{
c
(
vv
1
)
,c
(
vw
)
}
=
{
1
,
2
}
.
c
(
vv
1
) =
c
(
uu
1
) = 1
,c
(
vw
) =
c
(
uu
2
) = 2.
²
L
u
1
,v
1
˜
½
•
3
∆
−
1
^
(1
,α
)
(
u,v
)
-
V
Ú
´
,
α
∈{
4
,...,k
}
.
²
L
u
2
,w
˜
½
•
3
∆
−
2
^
(2
,α
)
(
u,v
)
-
V
Ú
´
,
α
∈{
4
,...,k
}
.
C
(
v
1
)=
{
4
,...,k
}∪{
1
}
=
L
\{
2
,
3
}
,
C
(
w
) =
{
4
,...,k
}∪
{
2
,
3
}
=
L
\{
1
}
,
C
(
v
1
)
∪
C
(
w
) = [
k
],
=
²
L
u
1
,v
1
˜
½
•
3
(1
,α
)
(
u,v
)
-
V
Ú
´
,
α
∈{
4
,...,k
}\
C
(
w
),
²
L
u
2
,w
˜
½
•
3
(2
,β
)
(
u,v
)
-
V
Ú
´
,
β
∈{
4
,...,k
}\
C
(
v
1
).
d
ž
Œ
^
α
/
>
vw
,
G
0
k
˜
‡
#
Ã
k
-
>
/Ú
c
0
,
…
|
C
0
(
u
)
∩
C
0
(
v
)
|
= 1,
†
œ
¹
2
?
Ø
a
q
,
G
•Ã
k
-
>
Œ
/
,
g
ñ
.
Ú
n
7[18]
-
f
•
˜
‡
4-
¡
,
P
‰
f
= [
xyzw
].
e
d
(
x
) =
d
(
z
) = 3,
K
d
(
y
)
,d
(
w
)
≥
5.
DOI:10.12677/aam.2021.1082762665
A^
ê
Æ
?
Ð
_
j
§
Á
öI
3.2.
=
£
-
G
•
½
n
1
4
‡
~
.
du
G
÷
v
Ø
¹
ƒ
i
-
,
…
5
,j
-
Ø
,
i
∈{
3
,
4
}
,j
∈{
4
,
6
}
,
K
k
e
¡
(
J
¤
á
:
(
P
1
)
z
‡
d
-
:
†
•
õ
b
d
2
c
‡
4
−
-
¡
'
é
;
(
P
2
)
e
d
(
f
) = 3,
K
†
f
ƒ
¡
þ
•
6
+
-
¡
;
(
P
3
)
e
d
(
f
) = 3 ,
…
δ
(
f
) = 2,
K
f
–
†
˜
‡
7
+
-
¡
ƒ
;
(
P
4
)
e
d
(
f
) = 4,
K
†
f
ƒ
¡
þ
•
6
+
-
¡
;
(
P
5
)
e
d
(
f
) = 5,
K
f
¡
•
5-
¡
½
7
+
-
¡
;
(
P
6
)
e
d
(
f
) = 5 ,
…
δ
(
f
) = 2,
K
f
–
†
˜
‡
7
+
-
¡
ƒ
.
ä
ó
1
2-
:
3
3-
¡
þ
,
e
m
3
(
v
)
•
Û
ê
,
K
m
7
+
(
v
)
≥
m
3
(
v
)+1
2
;
e
m
3
(
v
)
•
ó
ê
,
K
m
7
+
(
v
)
≥
m
3
(
v
)
2
.
Š
â
ë
Ï
²
¡
ã
Euler
ú
ª
|
V
|
+
|
F
|−|
E
|
=2
9
Ý
Ú
ú
ª
P
v
∈
V
(
G
)
d
(
v
)=
P
f
∈
F
(
G
)
d
(
f
)=
2
|
E
(
G
)
|
,
k
P
v
∈
V
(
G
)
(
d
(
v
)
−
4)+
P
f
∈
F
(
G
)
(
d
(
f
)
−
4) =
−
8
.
y
E
˜
‡
¼
ê
,
v
∈
V
(
G
)
ž
,
ω
(
v
)=
d
(
v
)
−
4,
f
∈
F
(
G
)
ž
,
ω
(
f
)=
d
(
f
)
−
4,
K
k
P
x
∈
V
(
G
)
S
F
(
G
)
ω
(
x
)=
−
8.
e
¡
Š
â
G
(
5
Ÿ
,
3
±
o
Ú
ØC
œ
¹
e
,
é
G
¥
:
Ú
¡
U
e
¡
=
5
K
?
1
=
£
,
˜
‡
#
¼
ê
ω
0
(
x
).
e
¡
ò
y
²
:
é
?
¿
x
∈
V
(
G
)
S
F
(
G
),
Ñ
k
ω
0
(
x
)
≥
0.
l
Ñ
X
e
g
ñ
:
0
≤
P
x
∈
V
(
G
)
S
F
(
G
)
ω
0
(
x
) =
P
x
∈
V
(
G
)
S
F
(
G
)
ω
(
x
) =
−
8
.
T
g
ñ
`
²
½
n
1
4
‡
~
G
Ø
•
3
,
l
½
n
1
¤
á
.
=
£
5
K
:
R1
z
‡
5
+
-
¡
f
‰
¡
þ
z
˜
‡
º:
=
d
(
f
)
−
4
d
(
f
)
.
R2
z
‡
5
+
-
:
v
‰
ƒ
2-
:
=
5
6
.
R3
z
‡
4-
:
v
‰
ƒ
3-
:
=
1
5
.
R4
z
‡
5
+
-
:
v
‰
ƒ
3-
:
=
1
3
.
R5
f
´
†
4
+
-
:
v
'
é
3-
¡
,
e
δ
(
f
)
≤
3,
K
v
‰
f
=
1
2
;
e
δ
(
f
)
≥
4,
K
v
‰
f
=
1
3
.
e
¡
k
y
é
∀
f
∈
F
(
G
),
Ñ
k
ω
0
(
f
)
≥
0.
d
(
f
)=3
ž
,
Š
â
R
5
k
ω
0
(
f
)
≥
d
(
f
)
−
4+min
{
2
×
1
2
,
3
×
1
3
}
=0;
d
(
f
)=4
ž
,
DOI:10.12677/aam.2021.1082762666
A^
ê
Æ
?
Ð
_
j
§
Á
öI
ω
0
(
f
) =
ω
(
f
) = 4
−
4 = 0;
d
(
f
)
≥
5
ž
,
d
R
1,
k
ω
0
(
f
) =
d
(
f
)
−
4
−
d
(
f
)
−
4
d
(
f
)
×
d
(
f
) = 0.
y
3
y
é
∀
v
∈
V
(
G
),
Ñ
k
ω
0
(
v
)
≥
0.
d
Ú
n
1
Œ
•
δ
(
G
)
≥
2.
(1)
d
(
v
) = 2,
ω
(
v
) =
−
2,
m
4
−
(
v
)
≤
1.
d
Ú
n
5
Œ
•
,
v
:
•
5
+
-
:
.
m
4
−
(
v
) = 0
ž
,
d
R
1
,R
2
k
ω
0
(
v
)
≥−
2+
min
{
2
×
1
5
,
1
5
+
3
7
}
+2
×
5
6
=
1
15
>
0.
m
4
−
(
v
)=1
ž
,
e
v
†
3-
¡
'
é
,
K
v
,
˜
‡
'
é
¡
•
7
+
-
¡
,
d
R
1
,R
2
k
ω
0
(
v
)
≥
−
2+
3
7
+2
×
5
6
=
2
21
>
0;
e
v
†
4-
¡
'
é
,
K
v
,
˜
‡
'
é
¡
•
6
+
-
¡
,
d
R
1
,R
2
k
ω
0
(
v
)
≥−
2+
1
3
+2
×
5
6
= 0.
(2)
d
(
v
) = 3,
ω
(
v
) =
−
1,
m
4
−
(
v
)
≤
1.
m
4
−
(
v
) = 0
ž
,
Ï
L
Ú
n
5
Œ
•
n
4
+
(
v
) = 3,
d
R
1
,R
3
,R
4
k
ω
0
(
v
)
≥−
1+3
×
1
5
+3
×
1
5
=
1
5
>
0.
m
4
−
(
v
)=1
ž
,
e
v
†
3-
¡
'
é
,
K
v
,
ü
‡
'
é
¡
•
6
+
-
¡
,
Ï
L
Ú
n
5
Ú
Ú
n
6
Œ
•
n
4
(
v
)=1
,n
5
+
(
v
)=2,
d
R
1
,R
3
,R
4
k
ω
0
(
v
)
≥−
1+ 2
×
1
3
+
1
5
+2
×
1
3
=
8
15
>
0;
e
v
†
4-
¡
'
é
,
K
v
,
ü
‡
'
é
¡
•
6
+
-
¡
,
Ï
L
Ú
n
5
Œ
•
n
4
+
(
v
)=3,
d
R
1
,R
3
k
ω
0
(
v
)
≥−
1+2
×
1
3
+3
×
1
5
=
4
15
>
0.
(3)
d
(
v
) = 4,
ω
(
v
) = 0,
m
4
−
(
v
)
≤
2.
m
4
−
(
v
) = 0
ž
,
Ï
L
Ú
n
5
Œ
•
n
2
(
v
) = 0
,n
3
(
v
)
≤
4,
d
R
1
,R
3
k
ω
0
(
v
)
≥
0+4
×
1
5
−
4
×
1
5
= 0.
m
4
−
(
v
)=1
ž
,
e
v
†
3-
¡
'
é
,
K
v
,
n
‡
'
é
¡
•
6
+
-
¡
,
Ï
L
Ú
n
5
Ú
Ú
n
6
Œ
•
n
3
(
v
)
≤
2,
d
R
1
,R
3
,R
5
k
ω
0
(
v
)
≥
0+3
×
1
3
−
1
3
−
2
×
1
5
=
4
15
>
0;
e
v
†
4-
¡
'
é
,
K
v
,
n
‡
'
é
¡
•
6
+
-
¡
,
Ï
L
Ú
n
5
Ú
Ú
n
7
Œ
•
n
3
(
v
)
≤
3,
d
R
1
,R
3
k
ω
0
(
v
)
≥
0+3
×
1
3
−
3
×
1
5
=
2
5
>
0.
m
4
−
(
v
)=2
ž
,
e
v
†
ü
‡
3-
¡
'
é
,
K
v
,
ü
‡
'
é
¡
•
6
+
-
¡
,
Ï
L
Ú
n
5
Ú
Ú
n
6
Œ
•
n
4
+
(
v
)=4,
d
R
1
,R
5
k
ω
0
(
v
)
≥
0+2
×
1
3
−
2
×
1
3
=0;
e
v
†
˜
‡
3-
¡
Ú
˜
‡
4-
¡
'
é
,
K
v
,
ü
‡
'
é
¡
•
6
+
-
¡
,
Ï
L
Ú
n
5 ,
Ú
n
6
Ú
Ú
n
7
Œ
•
n
3
(
v
)
≤
1,
d
R
1
,R
3
,R
5
k
ω
0
(
v
)
≥
0+2
×
1
3
−
1
3
−
1
5
=
2
15
>
0;
e
v
†
ü
‡
4-
¡
'
é
,
K
v
,
ü
‡
'
é
¡
•
6
+
-
¡
,
Ï
L
Ú
n
5
Ú
Ú
n
7
Œ
•
n
3
(
v
)
≤
2,
d
R
1
,R
3
k
ω
0
(
v
)
≥
0+2
×
1
3
−
2
×
1
5
=
4
15
>
0.
(4)
d
(
v
) = 5,
ω
(
v
) = 1,
m
4
−
(
v
)
≤
2.
(4.1)
m
4
−
(
v
) = 0.
e
v
v
k
2-
:
,
K
n
3
+
(
v
) = 5,
d
R
1
,R
4
k
ω
0
(
v
)
≥
1+5
×
1
5
−
5
×
1
3
=
1
3
>
0;
e
v
k
2-
:
,
K
Ï
L
Ú
n
3
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
3 = 2.
n
2
(
v
) = 2
ž
,
d
R
1
,R
2
k
ω
0
(
v
)
≥
1+4
×
1
5
+
3
7
−
2
×
5
6
=
59
105
>
0,
n
2
(
v
) = 1
,n
3
(
v
) = 1
ž
,
d
R
1
,R
2
,R
4
k
ω
0
(
v
)
≥
1+4
×
1
5
+
3
7
−
5
6
−
1
3
=
223
210
>
0.
(4.2)
m
4
−
(
v
) = 1.
e
v
†
3-
¡
'
é
,
K
v
,
o
‡
'
é
¡
•
6
+
-
¡
.
v
v
k
2 -
:
ž
,
Ï
L
Ú
n
5
Ú
Ú
n
6
Œ
•
n
3
(
v
)
≤
4,
d
R
1
,R
4
,R
5
k
ω
0
(
v
)
≥
1+4
×
1
3
−
1
2
−
4
×
1
3
=
1
2
>
0;
v
k
2-
:
ž
,
e
2-
:
†
3-
¡
'
é
,
K
Ï
L
Ú
n
4
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
4 = 1,
d
R
1
,R
2
,R
5
k
ω
0
(
v
)
≥
1+3
×
1
3
+
3
7
−
1
2
−
5
6
=
23
21
>
0;
e
2-
:
Ø
†
3-
¡
'
é
,
K
Ï
L
Ú
n
3
Œ
•
n
2
(
v
) +
n
3
(
v
)
≤
d
−
3=2,
d
R
1
,R
2
,R
4
,R
5
k
DOI:10.12677/aam.2021.1082762667
A^
ê
Æ
?
Ð
_
j
§
Á
öI
ω
0
(
v
)
≥
1+4
×
1
3
−
max
{
1
3
+2
×
5
6
,
1
2
+
5
6
+
1
3
}
=
1
3
>
0.
e
v
†
4-
¡
'
é
,
K
v
,
o
‡
'
é
¡
•
6
+
-
¡
.
v
v
k
2-
:
ž
,
Ï
L
Ú
n
5
Ú
Ú
n
7
Œ
•
n
3
(
v
)
≤
5,
d
R
1
,R
4
k
ω
0
(
v
)
≥
1 + 4
×
1
3
−
5
×
1
3
=
2
3
>
0;
v
k
2-
:
ž
,
Ï
L
Ú
n
3
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
3 = 2,
d
R
1
,R
2
,R
4
k
ω
0
(
v
)
≥
1+4
×
1
3
−
max
{
2
×
5
6
,
5
6
+
1
3
}
=
2
3
>
0.
(4.3)
m
4
−
(
v
) = 2.
e
v
†
ü
‡
3-
¡
'
é
,
K
v
,
n
‡
'
é
¡
•
6
+
-
¡
.
v
v
k
2-
:
ž
,
Ï
L
Ú
n
5
Ú
Ú
n
6
Œ
•
n
3
(
v
)
≤
3,
d
R
1
,R
4
,R
5
k
ω
0
(
v
)
≥
1+3
×
1
3
−
2
×
1
2
−
3
×
1
3
=0;
v
k
2-
:
ž
,
e
2-
:
†
3-
¡
'
é
,
K
Ï
L
Ú
n
4
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
4=1,
d
R
1
,R
2
,R
5
k
ω
0
(
v
)
≥
1 +2
×
1
3
+
3
7
−
1
2
−
1
3
−
5
6
=
3
7
>
0;
e
2-
:
Ø
†
3-
¡
'
é
,
K
Ï
L
Ú
n
3
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
3 = 2,
d
R
1
,R
2
,R
4
,R
5
k
ω
0
(
v
)
≥
1+3
×
1
3
−
1
2
−
1
3
−
5
6
−
1
3
= 0.
e
v
†
˜
‡
3-
¡
Ú
˜
‡
4-
¡
'
é
,
K
v
,
n
‡
'
é
¡
•
6
+
-
¡
.
v
v
k
2-
:
ž
,
Ï
L
Ú
n
5,
Ú
n
6
Ú
Ú
n
7
Œ
•
n
3
(
v
)
≤
4,
d
R
1
,R
4
,R
5
k
ω
0
(
v
)
≥
1+ 3
×
1
3
−
1
2
−
4
×
1
3
=
1
6
>
0;
v
k
2-
:
ž
,
e
2-
:
†
3-
¡
'
é
,
K
Ï
L
Ú
n
4
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
4=1,
d
R
1
,R
2
,R
5
k
ω
0
(
v
)
≥
1+2
×
1
3
+
3
7
−
1
2
−
5
6
=
16
21
>
0;
e
2-
:
Ø
†
3-
¡
'
é
,
K
Ï
L
Ú
n
3
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
3 = 2,
d
R
1
,R
2
,R
4
,R
5
k
ω
0
(
v
)
≥
1+3
×
1
3
−
max
{
1
3
+2
×
5
6
,
1
2
+
5
6
+
1
3
}
= 0.
e
v
†
ü
‡
4-
¡
'
é
,
K
v
,
n
‡
'
é
¡
•
6
+
-
¡
.
v
v
k
2-
:
ž
,
Ï
L
Ú
n
5
Ú
Ú
n
7
Œ
•
n
3
(
v
)
≤
5,
d
R
1
,R
4
k
ω
0
(
v
)
≥
1+3
×
1
3
−
5
×
1
3
=
1
3
>
0;
v
k
2-
:
ž
,
Ï
L
Ú
n
3
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
3 = 2,
d
R
1
,R
2
,R
4
k
ω
0
(
v
)
≥
1+3
×
1
3
−
max
{
2
×
5
6
,
5
6
+
1
3
}
=
1
3
>
0.
(5)
d
(
v
) =
d
≥
6,
ω
(
v
) =
d
−
4,
m
4
−
(
v
)
≤b
d
2
c
.
P
τ
•
v
'
é
¡
=
‰
v
o
Š
;
τ
(
f
→
v
)
•
¡
f
=
‰
v
Š
;
τ
(
v
→
u
)
•
:
v
=
‰
:
u
Š
.
(5.1)
m
4
−
(
v
) = 0.
(5.1.1)
n
2
(
v
) = 0.
d
R
1
,R
4
Œ
ω
0
(
v
)
≥
d
−
4+
1
5
d
−
1
3
d
=
13
15
d
−
4
>
0.
(5.1.2)
n
2
(
v
)
>
0.
Ï
L
Ú
n
3
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
3.
du
m
4
−
(
v
) = 0,
•
Ä
†
v
'
é
¡
•
5
+
-
¡
œ
¹
.
(a)
m
5
(
v
) = 0,
=
v
'
é
¡
þ
•
6
+
-
¡
.
d
R
1
,R
2
,R
4
Œ
ω
0
(
v
)
≥
d
−
4+
1
3
m
6
(
v
)+
3
7
m
7
+
(
v
)
−
5
6
n
2
(
v
)
−
1
3
n
3
(
v
)
≥
d
−
4+
1
3
d
−
5
6
(
d
−
3) =
1
2
d
−
3
2
>
0.
(b)
m
6
(
v
) = 0,
=
v
'
é
¡
þ
•
5-
¡
½
ö
7
+
-
¡
.
d
R
1
Œ
•
,
5-
¡
¦
Œ
U
õ
, 7
+
-
¡
¦
Œ
U
ž
,
τ
Œ
•
Š
,
du
¡
f
•
7-
¡
ž
τ
(
f
→
v
)
Š
'
¡
f
•
8
+
-
¡
ž
τ
(
f
→
v
)
Š
,
•
¦
τ
•
,
ò
7
+
-
¡
þ
w
Š
7-
¡
•
Ä
.
d
(
P
6)
Œ
•
,
e
2-
:
3
5-
¡
þ
,
K
T
5-
¡
–
†
˜
‡
7
+
-
¡
ƒ
.
n
2
(
v
)=0
ž
,
v
'
é
¡
DOI:10.12677/aam.2021.1082762668
A^
ê
Æ
?
Ð
_
j
§
Á
öI
þ
•
5-
¡
Œ
¦
τ
•
,
3
¦
τ
¦
Œ
U
c
J
e
O
\
2-
:
ê
þ
.
P
N
(
v
)=
{
v
1
,v
2
,...,v
d
}
,
f
1
=[
vv
d
...v
1
],
f
2
=[
vv
1
...v
2
],
f
i
=[
vv
i
−
1
...v
i
]
,
2
≤
i
≤
d
.
d
(
v
1
)=3
ž
,
τ
(
f
1
→
v
) +
τ
(
f
2
→
v
)
−
τ
(
v
→
u
)=
1
15
;
d
(
v
1
)=2
ž
,
τ
(
f
1
→
v
)+
τ
(
f
2
→
v
)
−
τ
(
v
→
u
) =
−
43
210
,
n
3
−
(
v
) =1
ž
,
ò
Ù
w
Š
2-
:
Œ
¦
v
=
Ñ
Š
•
õ
.
n
3
−
(
v
) =2
ž
,
e
d
(
v
1
) =
d
(
v
2
) =2,
K
v
'
é
¡
¥–
1
‡
5-
¡
ò
C
•
7
+
-
¡
,
d
ž
P
3
i
=1
τ
(
f
i
→
v
)
−
P
2
i
=1
τ
(
v
→
v
i
)
≥−
88
105
;
e
d
(
v
1
)=2
,d
(
v
2
)=3,
K
P
3
i
=1
τ
(
f
i
→
v
)
−
P
2
i
=1
τ
(
v
→
v
i
)=
−
71
210
;
e
d
(
v
1
)=
d
(
v
2
)= 3,
K
P
3
i
=1
τ
(
f
i
→
v
)
−
P
2
i
=1
τ
(
v
→
v
i
)=
−
1
15
,
n
3
−
(
v
)=2
ž
,
ò
Ù
þ
w
Š
2-
:
Œ
¦
v
=
Ñ
Š
•
õ
.
n
3
−
(
v
)
≥
3
œ
¹
?
Ø
Ó
þ
,
•
¦
v
=
Ñ
Š
•
õ
,
ò
v
:
¥
3
−
-
:
þ
w
‰
2-
:
•
Ä
,
=
k
n
2
(
v
)
≤
d
−
3.
e
n
2
(
v
)
•
Û
ê
,
K
m
7
+
(
v
)
≥
n
2
(
v
)+1
2
,
e
n
2
(
v
)
•
ó
ê
,
K
m
7
+
(
v
)
≥
n
2
(
v
)
2
.
n
2
(
v
)
•
Û
êž
,
d
R
1
,R
2
Œ
ω
0
(
v
)
≥
d
−
4+
1
5
m
5
(
v
)+
3
7
m
7
+
(
v
)
−
5
6
n
2
(
v
)
≥
d
−
4+
1
5
(
d
−
n
2
(
v
)+1
2
)+
3
7
×
n
2
(
v
)+1
2
−
5
6
n
2
(
v
) =
6
5
d
−
151
210
n
2
(
v
)
−
136
35
≥
6
5
d
−
151
210
(
d
−
3)
−
136
35
=
101
210
d
−
121
70
>
0.
n
2
(
v
)
•
ó
êž
,
d
R
1
,R
2
Œ
ω
0
(
v
)
≥
d
−
4+
1
5
m
5
(
v
)+
3
7
m
7
+
(
v
)
−
5
6
n
2
(
v
)
≥
d
−
4+
1
5
(
d
−
n
2
(
v
)
2
)+
3
7
×
n
2
(
v
)
2
−
5
6
n
2
(
v
) =
6
5
d
−
151
210
×
n
2
(
v
)
−
4
≥
6
5
d
−
151
210
(
d
−
3)
−
4 =
101
210
d
−
129
70
>
0.
(c)
v
'
é
¡
¥
5-, 6-,7
+
-
¡
þ
•
3
.
du
¡
f
•
7-
¡
ž
τ
(
f
→
v
)
Š
'
¡
f
•
8
+
-
¡
ž
τ
(
f
→
v
)
Š
,
•
¦
τ
•
,
ò
7
+
-
¡
þ
w
Š
7-
¡
•
Ä
,
=
•
Ä
v
'
é
¡
¥
5-,6-, 7-
¡
þ
•
3
œ
¹
.
du
5-,6-
¡
Ø
,
Œ
1
≤
m
5
(
v
)
≤
d
−
3, 1
≤
m
6
(
v
)
≤
d
−
3, 2
≤
m
7
(
v
)
≤
d
−
2.
P
x
•
5-
¡
C
•
6-
¡
ê
þ
,
y
•
7-
¡
C
•
6-
¡
ê
þ
.
d
(
b
)
Œ
•
,
m
6
(
v
) =0,
=
v
'
é
¡
•
5-
¡
½
7
+
-
¡
ž
, 5-
¡
¦
Œ
U
õ
, 7
+
-
¡
¦
Œ
U
Œ
y
τ
•
,
y
3
v
'
é
¡
¥
•
3
6-
¡
,
A
ò
5-
¡
½
7
+
-
¡
C
•
6-
¡
,
•
y
τ
¦
Œ
U
ò
(
b
)
¥
7
+
-
¡
þ
w
Š
7-
¡
.
e
Ø
U
C
(
b
)
¥
7-
¡
ê
þ
,
K
•
U
Ï
L
~
5-
¡
ê
þ
l
O
Œ
6-
¡
ê
þ
.
du
5-,6-
¡
Ø
,
…
1
≤
m
5
(
v
)
≤
d
−
3,
•
õ
d
−
m
7
(
v
)
−
1
‡
5-
¡
Œ
C
•
6-
¡
,
=
1
≤
x
≤
d
−
m
7
(
v
)
−
1.
Š
â
R
1
¡
f
d
5-
¡
C
•
6-
¡
τ
(
f
→
v
)
ò
C
Œ
2
15
,
Ï
L
~
5-
¡
ê
þ5
O
Œ
6-
¡
ê
þ
¬
¦
τ
C
Œ
.
e
Ø
U
C
(
b
)
¥
5-
¡
ê
þ
,
K
•
U
Ï
L
~
7-
¡
ê
þ
l
O
Œ
6-
¡
ê
þ
.
du
5-,6-
¡
Ø
…
v
2-
:
ê
þ
´
(
½
,
Ï
L
N
u
y
•
ª
7-
¡
ê
þ
ØC
, 5-
¡
ê
þ
~
,
†
þ
ã
?
Ø
ƒ
q
,
τ
C
Œ
.
y
Ï
L
U
C
(
b
)
¥
5-
¡
Ú
7-
¡
ê
þ5
O
Œ
6-
¡
ê
þ
.
e
ò
˜
‡
7-
¡
C
•
6-
¡
,
K
ò
¦
Ù
ƒ
ü
‡
5-
¡
C
•
6-
¡
½
˜
‡
5-
¡
C
•
6-
¡
,
˜
‡
5-
¡
C
•
7-
¡
½
ü
‡
5-
¡
C
•
7-
¡
.
e
˜
‡
5-
¡
C
•
6-
¡
,
˜
‡
5-
¡
C
•
7-
¡
,
du
5-,6-
¡
Ø
…
v
2-
:
ê
þ
´
(
½
,
Ï
L
N
u
y
•
ª
7-
¡
ê
þ
ØC
, 5-
¡
ê
þ
~
,
†
þ
ã
?
Ø
ƒ
q
,
τ
C
Œ
.
du
¡
f
d
5-
¡
C
•
6-
¡
τ
(
f
→
v
)
ò
C
Œ
2
15
,
¡
f
d
5-
¡
C
•
7-
¡
τ
(
f
→
v
)
ò
C
Œ
8
35
,
•
¦
τ
¦
Œ
U
=
•
Ä
ò
(
b
)
¥
7-
¡
C
•
6-
¡
ž
Ù
ƒ
ü
‡
5-
¡
C
•
6-
¡
œ
¹
,
d
ž
k
2
≤
y
+1
≤
x
≤
d
−
m
7
(
v
)
−
1,
du
¡
f
d
5-
¡
C
•
6-
¡
τ
(
f
→
v
)
ò
C
Œ
2
15
,
¡
f
d
7-
¡
C
•
6-
¡
τ
(
f
→
v
)
ò
2
21
,
Ï
L
Ó
ž
~
5-
¡
Ú
7-
¡
ê
þ5
O
Œ
6-
¡
ê
þ
•
¬
¦
τ
C
Œ
.
DOI:10.12677/aam.2021.1082762669
A^
ê
Æ
?
Ð
_
j
§
Á
öI
n
þ
,5-,6-, 7
+
-
¡
þ
•
3
ž
•
ª
Š
ò
Œ
u
(
b
)
œ
¹
e
•
ª
Š
,
=
ω
0
(
v
)
≥
0.
(5.2)
1
≤
m
4
−
(
v
)
≤b
d
2
c
.
(5.2.1)
n
2
(
v
) = 0.
d
R
1
,R
4
,R
5
Œ
ω
0
(
v
)
≥
d
−
4+
1
3
(
d
−
m
3
(
v
)
−
m
4
(
v
))
−
1
2
m
3
(
v
)
−
1
3
(
d
−
m
3
(
v
))=
d
−
1
2
m
3
(
v
)
−
1
3
m
4
(
v
)
−
4
≥
d
−
1
2
(
m
3
(
v
)+
m
4
(
v
))
−
4
≥
3
4
d
−
4
>
0.
(5.2.2)
n
2
(
v
)
>
0.
(a)
2-
:
†
3-
¡
'
é
.
Ï
L
Ú
n
4
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
4.
Š
â
ä
ó
1:
m
3
(
v
)
•
Û
êž
,
d
R
1
,R
2
,R
5
k
ω
0
(
v
)
≥
d
−
4+
3
7
×
m
3
(
v
)+1
2
+
1
3
×
(
d
−
m
4
−
(
v
)
−
m
3
(
v
)+1
2
)
−
1
2
m
3
(
v
)
−
5
6
(
d
−
4) =
1
2
d
−
11
14
m
3
(
v
)
−
1
3
m
4
(
v
)
−
13
21
≥
1
2
d
−
11
14
m
4
−
(
v
)
−
13
21
≥
3
28
d
−
13
21
>
0.
m
3
(
v
)
•
ó
êž
,
e
d
≥
7,
K
d
R
1
,R
2
,R
5
k
ω
0
(
v
)
≥
d
−
4+
3
7
×
m
3
(
v
)
2
+
1
3
×
(
d
−
m
4
−
(
v
)
−
m
3
(
v
)
2
)
−
1
2
m
3
(
v
)
−
5
6
(
d
−
4) =
1
2
d
−
11
14
m
3
(
v
)
−
1
3
m
4
(
v
)
−
2
3
≥
1
2
d
−
11
14
m
4
−
(
v
)
−
2
3
≥
3
28
d
−
2
3
>
0;
e
d
=6,
d
ž
m
3
(
v
) =2,
d
R
1
,R
2
,R
5
k
ω
0
(
v
)
≥
d
−
4+
3
7
×
m
3
(
v
)
2
+
1
3
×
(
d
−
m
4
−
(
v
)
−
m
3
(
v
)
2
)
−
1
2
m
3
(
v
)
−
5
6
(
d
−
4) =
1
2
d
−
11
14
m
3
(
v
)
−
1
3
m
4
(
v
)
−
2
3
=
1
2
d
−
1
3
m
4
(
v
)
−
11
7
−
2
3
≥
1
2
d
−
1
3
(
d
2
−
2)
−
47
21
=
1
3
d
+
2
3
−
47
21
=
1
3
d
−
11
7
=
3
7
>
0.
(b)
2-
:
Ø
†
3-
¡
'
é
.
Ï
L
Ú
n
3
Œ
•
n
2
(
v
)+
n
3
(
v
)
≤
d
−
3.
m
3
(
v
)=0
ž
,
d
R
1
,R
2
,R
5
k
ω
0
(
v
)
≥
d
−
4 +
1
3
×
(
d
−
m
4
−
(
v
))
−
5
6
(
d
−
3)
−
1
3
m
3
(
v
)=
1
2
d
−
2
3
m
3
(
v
)
−
1
3
m
4
(
v
)
−
3
2
=
1
2
d
−
1
3
m
4
(
v
)
−
3
2
≥
1
3
d
−
3
2
>
0.
m
3
(
v
)=1
ž
,
d
R
1
,R
2
,R
5
k
ω
0
(
v
)
≥
d
−
4 +
1
3
×
(
d
−
m
4
−
(
v
))
−
5
6
(
d
−
3)
−
1
3
m
3
(
v
)=
1
2
d
−
2
3
m
3
(
v
)
−
1
3
m
4
(
v
)
−
3
2
=
1
2
d
−
1
3
m
4
(
v
)
−
13
6
≥
1
3
d
−
11
6
>
0.
2
≤
m
3
(
v
)
≤b
d
2
c
ž
, 4
−
d
2
≤
m
3
(
v
)
−
m
4
(
v
)
≤
d
2
,
d
R
1
,R
2
,R
5
k
ω
0
(
v
)
≥
d
−
4+
1
3
×
(
d
−
m
4
−
(
v
))
−
5
6
(
d
−
2
m
3
(
v
))
−
1
3
(2
m
3
(
v
)
−
3)
−
1
3
m
3
(
v
) =
1
2
d
+
1
3
(
m
3
(
v
)
−
m
4
(
v
))
−
3
≥
1
2
d
+
1
3
(4
−
d
2
)
−
3 =
1
3
d
−
5
3
>
0.
n
þ
,
·
‚
:
−
8 =
X
x
∈
V
(
G
)
S
F
(
G
)
ω
(
x
) =
X
x
∈
V
(
G
)
S
F
(
G
)
ω
0
(
x
)
≥
0
.
g
ñ
,
ù
`
²
G
Ø
•
3
,
l
½
n
1
´
¤
á
.
ë
•
©
z
[1]Fiamˇc´ık, I. (1978)The Acyclic ChromaticClass ofGraphs.
MathematicaSlovaca
,
28
,139-145.
DOI:10.12677/aam.2021.1082762670
A^
ê
Æ
?
Ð
_
j
§
Á
öI
[2]Alon,N.,Mcdiarmid,C.J.H.andReed,B.A.(1991)AcyclicColoringofGraphs.
Random
StructuresandAlgorithms
,
2
,277-288.https://doi.org/10.1002/rsa.3240020303
[3]Molloy,M. and Reed,B.(1998) Further Algorithmic Aspects of the Local Lemma.
Proceedings
oftheThirtiethAnnualACMSymposiumontheTheoryofComputing
, Dallas, TX, May 1998,
524-529.https://doi.org/10.1145/276698.276866
[4]Fialho,P.M.S.,deLima,B.N.B.andProcacci,A.(2020)ANewBoundontheAcyclicEdge
ChromaticNumber.
DiscreteMathematics
,
343
,ArticleID:112037.
https://doi.org/10.1016/j.disc.2020.112037
[5]Shu,Q.,Wang,W.andWang,Y.(2013)AcyclicChromaticIndicesofPlanarGraphswith
GirthatLeast4.
JournalofGraphTheory
,
73
,386-399.https://doi.org/10.1002/jgt.21683
[6]Hou,J.,Wang,W.andZhang,X.(2013)AcyclicEdgeColoringofPlanarGraphswithGirth
atLeast5.
DiscreteAppliedMathematics
,
161
,2958-2967.
https://doi.org/10.1016/j.dam.2013.06.013
[7]Hud´ak,D.,Kardoˇs,F.,Luˇzar,B.,Sot´ak,R.and
ˇ
Skrekovski,R.(2012)AcyclicEdgeColoring
ofPlanarGraphswith∆Colors.
DiscreteAppliedMathematics
,
160
,1356-1368.
[8]Wang,W.,Shu,Q.,Wang,K.andWang,P.(2011)AcyclicChromaticIndicesofPlanar
GraphswithLargeGirth.
DiscreteAppliedMathematics
,
159
,1239-1253.
https://doi.org/10.1016/j.dam.2011.03.017
[9]Wang, Y. andSheng,P. (2014) ImprovedUpper Bound forAcyclic ChromaticIndexof Planar
Graphswithout4-Cycles.
JournalofCombinatorialOptimization
,
27
,519-529.
https://doi.org/10.1007/s10878-012-9524-5
[10]Wang,W.,Shu,Q.andWang,Y.(2013)AcyclicEdgeColoringofPlanarGraphswithout
4-Cycles.
JournalofCombinatorialOptimization
,
25
,562-586.
https://doi.org/10.1007/s10878-012-9474-y
[11]Shu,Q.,Wang,W.andWang,Y.(2012)AcyclicEdgeColoringofPlanarGraphswithout
5-Cycles.
DiscreteAppliedMathematics
,
160
,1211-1223.
https://doi.org/10.1016/j.dam.2011.12.016
[12]Hou,J.,Liu,G.andWu,J.(2012)AcyclicEdgeColoringofPlanarGraphswithoutSmall
Cycles.
GraphsandCombinatorics
,
28
,215-226.https://doi.org/10.1007/s00373-011-1043-0
[13]Xie, D.andWu,Y. (2012)AcyclicEdgeColoringofPlanarGraphswithoutAdjacentTriangles.
JournalofMathematicalResearchwithApplications
,
32
,407-414.
[14]
²
x
,
Ó
|
.
²
¡
ã
Ã
>
/Ú
[J].
ô
€
“
‰
Œ
ÆÆ
(
g
,
‰
Æ
‡
),2014,32(3):22-26.
[15]Wang,Y.,Shu,Q.andWu,J.(2014)AcyclicEdgeColoringofPlanarGraphswithouta3-
CycleAdjacenttoa6-Cycle.
JournalofCombinatorialOptimization
,
28
,692-715.
https://doi.org/10.1007/s10878-014-9765-6
DOI:10.12677/aam.2021.1082762671
A^
ê
Æ
?
Ð
_
j
§
Á
öI
[16]Shu,Q.,Lin,G.andMiyano,E.(2020)AcyclicEdgeColoringConjectureIsTrueonPlanar
GraphswithoutIntersectingTriangles.In:Chen,J.,Feng,Q.andXu,J.,Eds.,
Theoryand
ApplicationsofModelsofComputation
,Springer,Cham,426-438.
https://doi.org/10.1007/978-3-030-59267-736
[17]Fiedorowicz, A.(2012) AcyclicEdgeColouringofPlanarGraphs.
DiscreteAppliedMathemat-
ics
,
160
,1513-1523.https://doi.org/10.1016/j.dam.2012.02.018
[18]Wan, M. andXu,B. (2014) Acyclic EdgeColoring ofPlanarGraphswithoutAdjacent Cycles.
ScienceChinaMathematics
,
57
,433-442.https://doi.org/10.1007/s11425-013-4644-7
DOI:10.12677/aam.2021.1082762672
A^
ê
Æ
?
Ð