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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematicsA^êÆ?Ð,2021,10(8),2660-2672
PublishedOnlineAugust2021inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2021.108276
²¡ãÃ>/Ú
___jjj§§§ÁÁÁöööIII
∗
úô“‰ŒÆêƆOŽÅ‰ÆÆ§úô7u
ÂvFϵ2021c72F¶¹^Fϵ2021c721F¶uÙFϵ2021c84F
Á‡
éuãG˜‡>/Úc:E(G)→{1,2,...,k}§e÷v?¿ü^ƒ>Ñ/ØÓôÚ§…ã
GØ•3V Ú§Kc¡•ãG˜‡Ãk->/Ú"ãGÃ>ÚꕦãGk˜‡
Ã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
Aproperedgek-coloringisamappingc: E(G) →{1,2,...,k}suchthatanytwoadjacent
edgesreceivedifferentcolors. Aproperedgek-coloringcofGiscalledacyclicifthere
arenobichromaticcyclesinG.TheacyclicchromaticindexofG, denotedbyχ
0
a
(G),
isthesmallestintegerksuchthatGisacyclicallyedgek-colorable. Inthispaper, we
showthatifGisaplanargraphcontainingnoadjacenti-cyclesandwithouta5-cycle
adjacenttoaj-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),9g(G), éu²¡ãG˜‡¡f, ed(f)=k
(½d(f)≥k, ½d(f)≤k), K¡f•˜‡k-¡(½k
+
-¡, ½k
−
-¡). éu²¡ãG˜‡º:v,
ed(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, kc(x)6=c(y), …ãGØ•3
VÚ,ãGÃ>ÚꕦãGk˜‡Ãk->/Ú•êk,^χ
0
a
(G)L«.
FiamˇcikJÑ˜‡'u²¡ãÃ>/ÚͶߎ.
ߎ1[1]éu?¿²¡ãG,kχ
0
a
(G) ≤∆(G)+2.
ù‡ßŽ–8„vk)û.1991cAlon,McDiarmidÚReed[2]y²鲡ãG,k
χ
0
a
(G) ≤64∆;1998cMolloyÚReed[3]y²鲡ãG,kχ
0
a
(G) ≤16∆;2020cFialho[4]
<y²鲡ãG,kχ
0
a
(G) ≤3.569(∆−1).
éug(G) ≥4²¡ãG,Ó|,‘…Ú²x[5]y²χ
0
a
(G) ≤∆(G)+2;éug(G) ≥5
²¡ãG,ûï¹[6]<y²χ
0
a
(G)≤∆(G) + 1; Óc,ûï¹[6]<y²e•ŒÝ÷v
DOI:10.12677/aam.2021.1082762661A^êÆ?Ð
_j§ÁöI
∆(G)≥9,Kχ
0
a
(G)=∆(G);éug(G)≥6²¡ãG,Hud´ak[7]<y²e•ŒÝ÷v
∆(G) ≥6, Kχ
0
a
(G) =∆(G); éug(G) ≥7²¡ãG, ‘…,Ó|,¸Ú²[8]y²e•
ŒÝ÷v∆(G)≥5, Kχ
0
a
(G) =∆(G); éug(G) ≥8²¡ãG, ‘…,Ó|,¸Ú²[8]y
²e•ŒÝ÷v∆(G) ≥4, Kχ
0
a
(G) = ∆(G).
éuع4-²¡ãG,AcÚ•²[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.
éu3-,3-Ø²¡ãG, [13]<y²χ
0
a
(G) ≤∆(G)+5; éu3-,5-Ø²
¡ãG,²xÚÓ|[14]y²χ
0
a
(G)≤∆(G)+2; éu3-,6-Ø²¡ãG, ²x,Ó|
ÚÇïû[15]<y²χ
0
a
(G) ≤∆(G)+2.
éuÃn/²¡ãG, Ó|[16]<y²χ
0
a
(G) ≤∆(G)+2; éui-,j-؃,
Ù¥i,j∈{3,4}²¡ãG, AnnaFiedorowicz[17]y²χ
0
a
(G) ≤∆(G)+2.
©òy²e¡½n:
½n1eã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)|. PN
k
(v)={x∈N(v)|d(x)=k}, …n
k
(v)=|N
k
(v)|. eº:v÷vd(v)=k, …v
†uƒ, K¡v•uk-:.
éu¡f∈F(G),^M(v)L«†vƒ'é¡8Ü,PM
k
(v)={f∈M(v)|d(f)=k},
…m
k
(v)=|M
k
(v)|. ^b(f) L«¡f>., eu
1
,u
2
,...,u
n
•b(f) þU^Sü:, KP‰
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α,βùü«ôÚOXÚ>¤|¤´, e(α,β)-VÚ´"à©O•
:uÚ:v,Kòù´P‰(α,β)
(u,v )
-VÚ´.
3.½n1y²
3.1.4‡~5Ÿ
©Ì‡ÏL=£•{5y²½n1.ãG´½n1¥¦|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. e5, ·‚&?G(
5Ÿ.
DOI:10.12677/aam.2021.1082762662A^êÆ?Ð
_j§ÁöI
Ún1²¡ã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
. ÏLNc
i
¦†v'é>/ØÓôÚ, ù
žk‡ôÚŒ±òãG/Ð,gñ.
Ún2G¥2-:؆3
−
-:ƒ.
y²-v•˜‡2-:, u´†vƒ3
−
-:,•?Ød(u) = 3œ¹, d(u) = 2œ¹Ón
Œ. PN(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ñ.
Ún3v•ãG˜‡4
+
-:,en
2
(v) = 1,Kn
2
(v)+n
3
(v) ≤d−3.
y²bn
2
(v) +n
3
(v)≥d−2.PN(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«œ¹:
œ¹1c(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ñ.
œ¹2c(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ñ.
œ¹3c(v
1
v
0
1
) ∈{d−1,d}
Ø”˜„5, -c(v
1
v
0
1
) = d. ²Lv
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 aq,Gk˜‡Ãk->/Ú,gñ.
Ún4v•ãG˜‡d-:,u•v2-:,eu†3-¡'é,Kd≥5,…n
2
(v)+n
3
(v) ≤
d−4.
y²Äky²d≥5.
d= 4,PN(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.1082762663A^êÆ?Ð
_j§ÁöI
dÚn2, d(v
1
) ≥4, -c(vv
i
) = i,i∈{1,2,3}.•Äe¡ü«œ¹:
œ¹1c(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) = α, Ïdk«ôÚŒòãG/Ð, gñ.
œ¹2c(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) = α,Ïdk«ôÚŒòãG/Ð, gñ.
y3y²n
2
(v)+n
3
(v) ≤d−4.
n
2
(v)+n
3
(v) ≥d−3. PN(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«œ¹:
œ¹1c(uv
1
)/∈{2,...,d−1}
>uvB^ÚF(uv)÷v: |F(uv)|≤|C(u)∪C(v)|≤d(u)−1+d(v)−1 = d<k,Ïdk«
ôÚŒòãG/Ð, gñ.
œ¹2c(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, Ïdk«ôÚŒòãG/Ð,gñ.
œ¹3c(uv
1
) ∈{d−2,d−1}
Ø”˜„5,c(uv
1
)=d−1.K•3˜^²Lv
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•3i
0
,2 ≤i
0
≤d−3, …i
0
/∈C(v
1
),džŒ^i
0
-/>uv
1
,†œ¹2aq,Gk˜‡Ã
k->/Ú,gñ.
Ún5[18]éu?¿>uv∈E(G), kd(u)+d(v) ≥7.
Ún6-f•˜‡3-¡, P‰f= [uvw].ed(v) = 3,Kd(u),d(w) ≥5.
y²dÚn5,ed(v) = 3,Kd(u) ≥4,d(w) ≥4.-d(u) = 4,N(u) = {v,w,u
1
,u
2
},N(v) =
{u,w,v
1
}. duGعƒ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.1082762664A^êÆ?Ð
_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.²Lv
1
,u
1
˜½•3∆−2^(1,α)
(u,v )
-VÚ´,α∈{5,...,k}.e•
3γ∈{5,...,k}, …²Lv
1
,u
1
Ã(1,γ)
(u,v )
-VÚ´, KŒ-c(uv)=γ, c=•G˜‡Ãk->
/Ú,gñ.{1,5,...,k}⊆C(v
1
).
e3/∈C(v
1
),KŒ^3-/>vv
1
,dž²Lv
1
,w˜½•3∆−2^(3,β)
(u,v )
-VÚ´,
β∈{5,...,k}. e•3γ∈{5,...,k},…²Lv
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.
²Lv
1
,w˜½•3∆ −2^(3,β)
(u,v )
-VÚ´,β∈{5,...,k}.e•3γ∈{5,...,k},…
²Lv
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) ?Øaq,c•G˜‡Ãk->/Ú,gñ.
(3)c(vw) ∈{c(uu
1
),c(uu
2
)}.
-c(vw)=c(uu
1
)=1,c(vv
1
)=4.²Lw,u
1
˜½•3∆ −2^(1,α)
(u,v )
-VÚ´,α∈
{5,...,k}. e•3γ∈{5,...,k},…²Lw,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) ?Øaq,c•G˜‡Ãk->/Ú,gñ.
œ¹3|C(u)∩C(v)|= 2
(1)c(vv
1
) = 3,c(vw) = 1.
²Lu
1
,w˜½•3∆−1^(1,α)
(u,v )
-VÚ´,α∈{4,...,k}.e•3γ ∈{4,...,k},
…²Lu
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.
²Lu
1
,v
1
˜½•3∆ −1^(1,α)
(u,v )
-VÚ´,α∈{4,...,k}. ²Lu
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],=²Lu
1
,v
1
˜½•3(1,α)
(u,v )
-VÚ´,α∈{4,...,k}\C(w),
²Lu
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 ?Øaq,G•Ãk->Œ/, gñ.
Ún7[18]-f•˜‡4-¡, P‰f= [xyzw].ed(x) = d(z) = 3,Kd(y),d(w) ≥5.
DOI:10.12677/aam.2021.1082762665A^êÆ?Ð
_j§ÁöI
3.2.=£
-G•½n1 4‡~.duG÷vعƒi-, …5,j-Ø, i∈{3,4},j∈{4,6}, K
ke¡(J¤á:
(P
1
)z‡d-:†•õb
d
2
c‡4
−
-¡'é;
(P
2
)ed(f) = 3, K†fƒ¡þ•6
+
-¡;
(P
3
)ed(f) = 3 ,…δ(f) = 2,Kf–†˜‡7
+
-¡ƒ;
(P
4
)ed(f) = 4, K†fƒ¡þ•6
+
-¡;
(P
5
)ed(f) = 5, Kf¡•5-¡½7
+
-¡;
(P
6
)ed(f) = 5 ,…δ(f) = 2,Kf–†˜‡7
+
-¡ƒ.
äó12-:33-¡þ, em
3
(v)•Ûê,Km
7
+
(v) ≥
m
3
(v )+1
2
;em
3
(v)•óê,Km
7
+
(v) ≥
m
3
(v )
2
.
Šâëϲ¡ãEulerúª|V|+ |F|−|E|=29ÝÚúª
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,
Kk
P
x∈V(G)
S
F(G)
ω(x)=−8.e¡ŠâG(5Ÿ,3±oÚØCœ¹e,éG¥
:Ú¡Ue¡=5K?1=£,˜‡#¼êω
0
(x).e¡òy²:é?
¿x∈V(G)
S
F(G),Ñkω
0
(x) ≥0.lÑXegñ:
0 ≤
P
x∈V(G)
S
F(G)
ω
0
(x) =
P
x∈V(G)
S
F(G)
ω(x) = −8.
Tgñ`²½n14‡~GØ•3,l½n1 ¤á.
=£5K:
R1z‡5
+
-¡f‰¡þz˜‡º:=
d(f)−4
d(f)
.
R2z‡5
+
-:v‰ƒ2-:=
5
6
.
R3z‡4-:v‰ƒ3-:=
1
5
.
R4z‡5
+
-:v‰ƒ3-:=
1
3
.
R5f´†4
+
-:v'é3-¡, eδ(f) ≤3,Kv‰f=
1
2
;eδ(f) ≥4, Kv‰f=
1
3
.
e¡kyé∀f∈F(G),Ñkω
0
(f) ≥0.
d(f)=3ž,ŠâR5kω
0
(f)≥d(f)−4+min{2×
1
2
,3×
1
3
}=0;d(f)=4ž,
DOI:10.12677/aam.2021.1082762666A^êÆ?Ð
_j§ÁöI
ω
0
(f) = ω(f) = 4−4 = 0; d(f) ≥5ž,dR1, kω
0
(f) = d(f)−4−
d(f)−4
d(f)
×d(f) = 0.
y3yé∀v∈V(G),Ñkω
0
(v) ≥0. dÚn1 Œ•δ(G) ≥2.
(1)d(v) = 2,ω(v) = −2,m
4
−
(v) ≤1.
dÚn5Œ•, v:•5
+
-:.
m
4
−
(v) = 0ž, dR1,R2 kω
0
(v) ≥−2+min{2×
1
5
,
1
5
+
3
7
}+2×
5
6
=
1
15
>0.
m
4
−
(v)=1ž,ev†3-¡'é,Kv,˜‡'é¡•7
+
-¡,dR1,R2kω
0
(v)≥
−2+
3
7
+2×
5
6
=
2
21
>0;ev†4-¡'é,Kv,˜‡'é¡•6
+
-¡,dR1,R2k
ω
0
(v) ≥−2+
1
3
+2×
5
6
= 0.
(2)d(v) = 3, ω(v) = −1, m
4
−
(v) ≤1.
m
4
−
(v) = 0ž,ÏLÚn5Œ•n
4
+
(v) = 3,dR1,R3,R4kω
0
(v) ≥−1+3×
1
5
+3×
1
5
=
1
5
>0.
m
4
−
(v)=1ž,ev†3-¡'é,Kv,ü‡'é¡•6
+
-¡,ÏLÚn5ÚÚn6
Υn
4
(v)=1,n
5
+
(v)=2,dR1,R3,R4kω
0
(v)≥−1+ 2×
1
3
+
1
5
+2 ×
1
3
=
8
15
>0;
ev†4-¡'é,Kv,ü‡'é¡•6
+
-¡,ÏLÚn5Œ•n
4
+
(v)=3,dR1,R3k
ω
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Ún5Œ•n
2
(v) = 0,n
3
(v) ≤4,dR1,R3kω
0
(v) ≥0+4×
1
5
−4×
1
5
= 0.
m
4
−
(v)=1 ž, ev†3-¡'é, Kv,n‡'é¡•6
+
-¡, ÏLÚn5 ÚÚn6 Œ•
n
3
(v) ≤2,dR1,R3,R5kω
0
(v) ≥0+3×
1
3
−
1
3
−2×
1
5
=
4
15
>0;ev†4-¡'é,Kv,n‡
'é¡•6
+
-¡,ÏLÚn5ÚÚn7Œ•n
3
(v) ≤3,dR1,R3kω
0
(v) ≥0+3×
1
3
−3×
1
5
=
2
5
>0.
m
4
−
(v)=2 ž, ev†ü‡3-¡ 'é, Kv,ü‡'é ¡•6
+
-¡, ÏLÚn5 ÚÚn6
Υn
4
+
(v)=4, dR1,R5 kω
0
(v)≥0+2 ×
1
3
−2×
1
3
=0;ev†˜‡3-¡Ú˜‡4-¡'é,
Kv,ü‡'é¡•6
+
-¡, ÏLÚn5 , Ún6 ÚÚn7 Œ•n
3
(v)≤1,dR1,R3,R5 k
ω
0
(v) ≥0+2×
1
3
−
1
3
−
1
5
=
2
15
>0; ev†ü‡4-¡'é,Kv,ü‡'é¡•6
+
-¡,ÏLÚ
n5ÚÚn7 Œ•n
3
(v) ≤2, dR1,R3 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.
evvk2-:,Kn
3
+
(v) = 5,dR1,R4kω
0
(v) ≥1+5×
1
5
−5×
1
3
=
1
3
>0;evk2-:,
KÏLÚn3Œ•n
2
(v)+n
3
(v) ≤d−3 = 2.n
2
(v) = 2ž,dR1,R2kω
0
(v) ≥1+4×
1
5
+
3
7
−2×
5
6
=
59
105
>0, n
2
(v) = 1,n
3
(v) = 1ž, dR1,R2,R4 kω
0
(v) ≥1+4×
1
5
+
3
7
−
5
6
−
1
3
=
223
210
>0.
(4.2)m
4
−
(v) = 1.
ev†3-¡'é,Kv,o‡'é¡•6
+
-¡.vvk2 -:ž, ÏLÚn5 ÚÚn6Œ•
n
3
(v) ≤4,dR1,R4,R5kω
0
(v) ≥1+4×
1
3
−
1
2
−4×
1
3
=
1
2
>0;vk2-:ž,e2-:†3-¡'é,
KÏLÚn4Œ•n
2
(v)+n
3
(v) ≤d−4 = 1,dR1,R2,R5kω
0
(v) ≥1+3×
1
3
+
3
7
−
1
2
−
5
6
=
23
21
>0;
e2-:؆3-¡'é,KÏLÚn3Œ•n
2
(v) + n
3
(v)≤d−3=2,dR1,R2,R4,R5k
DOI:10.12677/aam.2021.1082762667A^êÆ?Ð
_j§ÁöI
ω
0
(v) ≥1+4×
1
3
−max{
1
3
+2×
5
6
,
1
2
+
5
6
+
1
3
}=
1
3
>0.
ev†4-¡'é, Kv,o‡'é¡•6
+
-¡. vvk2-:ž, ÏLÚn5ÚÚn7 Œ
•n
3
(v)≤5,dR1,R4 kω
0
(v)≥1 + 4×
1
3
−5 ×
1
3
=
2
3
>0;vk2-:ž, ÏLÚn3Œ•
n
2
(v)+n
3
(v) ≤d−3 = 2, dR1,R2,R4kω
0
(v) ≥1+4×
1
3
−max{2×
5
6
,
5
6
+
1
3
}=
2
3
>0.
(4.3)m
4
−
(v) = 2.
ev†ü‡3-¡'é,Kv,n‡'é¡•6
+
-¡.vvk2-:ž,ÏLÚn5Ú
Ún6Œ•n
3
(v)≤3,dR1,R4,R5kω
0
(v)≥1+3 ×
1
3
−2 ×
1
2
−3 ×
1
3
=0;vk2-
:ž,e2-:†3-¡'é,KÏLÚn4Œ•n
2
(v)+n
3
(v)≤d−4=1,dR1,R2,R5
kω
0
(v)≥1 +2 ×
1
3
+
3
7
−
1
2
−
1
3
−
5
6
=
3
7
>0;e2-:؆3-¡'é,KÏLÚn3Œ•
n
2
(v)+n
3
(v) ≤d−3 = 2, dR1,R2,R4,R5kω
0
(v) ≥1+3×
1
3
−
1
2
−
1
3
−
5
6
−
1
3
= 0.
ev†˜‡3-¡Ú˜‡4-¡'é, Kv,n‡'é¡•6
+
-¡. vvk2-:ž,ÏLÚn
5, Ún6 ÚÚn7 Œ•n
3
(v)≤4, dR1,R4,R5 kω
0
(v)≥1+ 3×
1
3
−
1
2
−4 ×
1
3
=
1
6
>0;vk
2-:ž, e2-:†3-¡'é, KÏLÚn4 Œ•n
2
(v)+ n
3
(v)≤d−4=1, dR1,R2,R5 k
ω
0
(v) ≥1+2×
1
3
+
3
7
−
1
2
−
5
6
=
16
21
>0;e2-:؆3-¡'é,KÏLÚn3Œ•n
2
(v)+n
3
(v) ≤
d−3 = 2,dR1,R2,R4,R5 kω
0
(v) ≥1+3×
1
3
−max{
1
3
+2×
5
6
,
1
2
+
5
6
+
1
3
}= 0.
ev†ü‡4-¡'é, Kv,n‡'é¡•6
+
-¡. vvk2-:ž,ÏLÚn5 ÚÚn7
Υn
3
(v)≤5, dR1,R4 kω
0
(v)≥1+3 ×
1
3
−5 ×
1
3
=
1
3
>0; vk2-:ž, ÏLÚn3 Œ•
n
2
(v)+n
3
(v) ≤d−3 = 2, dR1,R2,R4kω
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.
dR1,R4Œω
0
(v) ≥d−4+
1
5
d−
1
3
d=
13
15
d−4 >0.
(5.1.2)n
2
(v) >0.
ÏLÚn3 Œ•n
2
(v)+n
3
(v) ≤d−3. dum
4
−
(v) = 0,•Ä†v'é¡•5
+
-¡œ
¹.
(a)m
5
(v) = 0,=v'é¡þ•6
+
-¡.
dR1,R2,R4Œω
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
+
-¡.
dR1Œ•, 5-¡¦ŒUõ, 7
+
-¡¦ŒUž,τŒ•Š, du¡f•7-¡žτ(f→v)
Š'¡f•8
+
-¡žτ(f→v)Š, •¦τ•, ò7
+
-¡þwŠ7-¡•Ä.
d(P6) Œ•, e2-:35-¡ þ, KT5-¡–†˜‡7
+
-¡ƒ. n
2
(v)=0 ž, v'é¡
DOI:10.12677/aam.2021.1082762668A^êÆ?Ð
_j§ÁöI
þ•5-¡Œ¦τ•, 3¦τ¦ŒU cJeO\2-:êþ. PN(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 ž, ed(v
1
) =d(v
2
) =2,Kv'é¡¥–
1 ‡5-¡òC•7
+
-¡, dž
P
3
i=1
τ(f
i
→v)−
P
2
i=1
τ(v→v
i
)≥−
88
105
; ed(v
1
)=2,d(v
2
)=3, K
P
3
i=1
τ(f
i
→v) −
P
2
i=1
τ(v→v
i
)=−
71
210
; ed(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-:•Ä,=kn
2
(v) ≤d−3. en
2
(v)
•Ûê,Km
7
+
(v) ≥
n
2
(v )+1
2
,en
2
(v)•óê, Km
7
+
(v) ≥
n
2
(v )
2
.
n
2
(v)•Ûêž, dR1,R2Œω
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)•óêž, dR1,R2Œω
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œ¹.du5-,6-¡Ø,Œ
1 ≤m
5
(v) ≤d−3, 1 ≤m
6
(v) ≤d−3, 2 ≤m
7
(v) ≤d−2. Px•5-¡C•6-¡êþ, y•7-¡
C•6-¡êþ.
d(b) Υ,m
6
(v) =0, =v'é¡•5-¡½7
+
-¡ž, 5-¡¦ŒUõ, 7
+
-¡¦ŒUŒy
τ•,y3v'é¡¥• 36-¡, Aò5-¡½7
+
-¡C•6-¡,•yτ¦ŒUò(b) ¥7
+
-
¡þwŠ7-¡.
eØUC(b) ¥7-¡êþ,K•UÏL~5-¡êþlOŒ6-¡êþ. du5-,6-¡Ø
, …1≤m
5
(v) ≤d−3, •õd−m
7
(v)−1 ‡5-¡ŒC•6-¡, =1 ≤x≤d−m
7
(v)−1. Š
âR1 ¡fd5-¡C•6-¡τ(f→v) òCŒ
2
15
, ÏL~5-¡êþ5OŒ6-¡êþ¬¦
τCŒ.
eØUC(b) ¥5-¡êþ,K•UÏL~7-¡êþlOŒ6-¡êþ. du5-,6-¡Ø
…v2-:êþ´(½, ÏLNuy•ª7-¡êþØC, 5-¡êþ~,†þã?؃q,
τCŒ.
yÏLUC(b) ¥5-¡Ú7-¡êþ5OŒ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-¡, du5-,6-¡Ø…v2-:êþ´(½,ÏLNuy•ª
7-¡êþØC, 5-¡êþ~, †þã?؃q, τCŒ. du¡fd5-¡C•6-¡τ(f→v) òCŒ
2
15
, ¡fd5-¡C•7-¡τ(f→v) òCŒ
8
35
, •¦τ¦ŒU=•Äò(b) ¥7-¡C•6-¡
žÙƒü‡5-¡C•6-¡œ¹, džk2≤y+1≤x≤d−m
7
(v)−1, du¡fd5-¡C•
6-¡τ(f→v) òCŒ
2
15
, ¡fd7-¡C•6-¡τ(f→v) ò 
2
21
, ÏLÓž~5-¡Ú7-¡
êþ5OŒ6-¡êþ•¬¦τCŒ.
DOI:10.12677/aam.2021.1082762669A^êÆ?Ð
_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.
dR1,R4,R5Œω
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Ún4Œ•n
2
(v)+n
3
(v) ≤d−4. Šâäó1:
m
3
(v)•Ûêž,dR1,R2,R5kω
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)•óêž,ed≥7, KdR1,R2,R5 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,dR1,R2,R5kω
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Ún3Œ•n
2
(v)+n
3
(v) ≤d−3.
m
3
(v)=0ž,dR1,R2,R5 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ž,dR1,R2,R5 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
, dR1,R2,R5 kω
0
(v) ≥d−4+
1
3
×(d−
m
4
−
(v))−
5
6
(d−2m
3
(v))−
1
3
(2m
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½n1 ´¤á.
ë•©z
[1]Fiamˇc´ık, I. (1978)The Acyclic ChromaticClass ofGraphs. MathematicaSlovaca, 28,139-145.
DOI:10.12677/aam.2021.1082762670A^êÆ?Ð
_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.1082762671A^êÆ?Ð
_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.1082762672A^êÆ?Ð

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