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

期刊菜单

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

文章导航

  • ●Abstract
  • ●Full-Text PDF
  • ●Full-Text HTML
  • ●Full-Text ePUB
  • ●Linked References
  • ●How to Cite this Article
AdvancesinAppliedMathematicsA^êÆ?Ð,2022,11(1),238-245
PublishedOnlineJanuary2022inHans.http://www.hanspub.org/journal/aam
https://doi.org/10.12677/aam.2022.111030
˜a²¡ã¥çôš
{{{bbb
1
§§§uuu²²²
2
1
úô“‰ŒÆêƆOŽÅ‰ÆÆ§úô7u
2
ôÜ“‰ŒÆêƆÚOÆ§ôÜH
ÂvFϵ2021c128F¶¹^Fϵ2022c17F¶uÙFϵ2022c121F
Á‡
鉽>/ÚãG§eãGz^>ôÚÑØÓ§KG´çô"鉽ãGÚH§H3
Gþanti-Ramsey ê§PŠAR(G,H)§L«ãG¥Ø•¹?ÛÓuHçôfã•Œ
>/Úê"©Ì‡ïÄT
−
n
¥šanti-Ramsey ê"
'…c
š§çôã§Anti-Ramseyê
RainbowMatchingsinPlanarGraphs
RuiYu
1
,HuapingWang
2
1
CollegeofMathematicsandComputerScience,ZhejiangNormalUniversity,JinhuaZhejiang
2
SchoolofMathematicsandStatistics,JiangxiNormalUniversity,NanchangJiangxi
Received:Dec.18
th
,2021;accepted:Jan.7
th
,2022;published:Jan.21
st
,2022
Abstract
Wecallanedge-coloredgraphGrainbow,ifallofitsedgeshavedifferentcolors.
©ÙÚ^:{b,u².˜a²¡ã¥çôš[J].A^êÆ?Ð,2022,11(1):238-245.
DOI:10.12677/aam.2022.111030
{b§u²
Theanti-RamseynumberofthegraphHinG,denotedbyAR(G,H),isthemaximum
number ofcolors inan edge-coloringofGwhichdoes notcontainanyrainbowsubgraph
isomorphicto H.Inthispaper,weconsidertheanti-Ramseynumberformatchings
inplanargraphsT
−
n
.
Keywords
Matching,RainbowGraph,Anti-RamseyNumber
Copyright
c
2022byauthor(s)andHansPublishersInc.
This work is licensed undertheCreative Commons Attribution InternationalLicense(CCBY4.0).
http://creativecommons.org/licenses/by/4.0/
1.Úó
鉽>/ÚãG,eGz^>ôÚÑØÓ,KG´çô.鉽ãGÚH,H3
Gþanti-Ramsey ê,PŠAR(G,H),L«ãG¥Ø•¹?ÛÓuHçôfã•Œ>/
Úê.Anti-Ramsey¯K•@dErd˝os <JÑ[1].Cc5, ²¡ã¥šanti-Ramsey ¯Kk
õ?Ð[2][3].Jendrol
0
[4]<ÄkéT
n
¥šanti-Ramseyê¯K?1ïÄ,Ù¥T
n
•
n‡:²¡n¿©ã.¦‚T
n
¥šanti-Ramseyêþe.,þe.ƒLŒ.
ˆIÆö—åu þ.Úe.ƒmå.•ª,Qin<[5](½T
n
¥šanti-Ramsey
êO(Š.©·‚•ÄT
−
n
¥šanti-Ramsey ê.Ù¥T
−
n
•T
n
íK˜^>,¡•o
²¡ã,w,k|E(T
−
n
)|= 3n−7.
2.ý•£
ÚÚÚnnn2.1.鉽>/ÚãG,-d•G•Œ çôšê.@o•3˜‡:8S∈V(G) ¦
d=
1
2
(n−(o(G−S)−|S|)),Ù¥o(H) •HÛ©|ê,Û©|äÏf.5.
鉽>/ÚãG,XJé?¿v∈V(G),G−vÑk{š,@o·‚¡GäkÏf
.5.
ÚÚÚnnn2.2.鉽>/ÚãG.XJG•¹˜‡çôov
1
v
2
v
3
v
4
v
1
…G−{v
1
,v
2
,v
3
,v
4
}¥„
•3>,@oG•¹˜‡çô3K
2
.
ÚÚÚnnn2.3.鉽>/ÚãG.XJG•¹˜‡çô8v
1
v
2
v
3
v
4
v
5
v
6
v
1
…G−{v
1
,v
2
,v
3
,v
4
,v
5
,v
6
}
¥„•3>,@oG•¹˜‡çô4K
2
.
DOI:10.12677/aam.2022.111030239A^êÆ?Ð
{b§u²
3.çô3K
2
Ú4K
2
½½½nnn3.1.AR(T
−
6
,3K
2
) = 7 .
y².Äky²e..˜‡ãG∈T
−
6
,-G:8•{v
1
,v
2
,v
3
,v
4
,v
5
,v
6
},G>8•
E(G) = {v
1
v
2
,v
3
v
4
,v
4
v
5
}∪{v
1
v
i
,v
2
v
i
|3 ≤i≤6}.éuãG,ò>v
3
v
4
,v
1
v
3
,v
1
v
6
,v
2
v
3
,v
3
v
6
/ôÚ
1,•e>/6 «ØÓ ôÚ(•„ã1).dž,·‚^7 «ôÚ5/,ãG¥Ø¹çô3K
2
.
dde.±y².
Figure1.ThecoloringofT
−
6
ã1.T
−
6
/Ú
Figure2.s=1,a
1
=3
ã2.s=1,a
1
=3
éuþ., ·‚^‡y{.b^8«ôÚ5/T
−
6
>, džG¥Ø¹çô3K
2
.w,,T
−
6
¥
kçô2K
2
.-G´T
−
6
çô)¤f ã,G>êE(G)= 8.dÚn2.1,•3V(G)˜‡f8
S,¦o(G−S)−|S|= 2.-|S|= s,o(G−S)−|S|= q.-G−SÛ©|•A
1
,A
2
,···,A
q
,
Ù¥|A
i
|=a
i
(1≤i≤q),Ø”˜„5,·‚a
1
≥a
2
≥···≥a
q
≥1.-G−Só©|•
C(G) = G−
q
S
i=1
V(A
i
)∪S.duq= s+2 …s+q≤6,Ïd0 ≤s≤2.
es=0,q=2.XJa
1
≤3,@o|E(G)|≤6<8,†bgñ.Ïd,C(G)=∅,a
1
=5,
a
2
=1,|E(G)|≤3 ×5−7=8.dž,·‚V(A
1
)={u
1
,u
2
,u
3
,u
4
,u
5
},V(A
2
)={v
2
}.d
|E(V(A
1
))|=8 Υ,V(A
1
) ¥–•3n‡:,Ø”•u
1
,u
2
,u
3
,¦A
1
−u
i
(i=1,2,3)•¹
˜‡çôo.3T
−
6
¥,:v
2
†V(A
1
) ¥n‡ :ƒ,•Ò´`v
2
–†{u
1
,u
2
,u
3
}¥˜
‡:ƒ,Ø”•u
1
.dÚn2.2,T
−
6
¹k˜‡çô3K
2
,†bgñ.
DOI:10.12677/aam.2022.111030240A^êÆ?Ð
{b§u²
Figure3.s=2,a
1
=3
ã3.s=2,a
1
=3
es=1,q=3.XJa
1
≤1,@o|E(G)|≤6<8,†bgñ.Ïd,C(G)=∅,
a
1
=3,a
2
=a
3
=1,|E(G)|≤5+ 3=8.dž,·‚S={w},V(A
1
)={u
1
,u
2
,u
3
},
V(A
i
)=v
i
(i=2,3)(•„ã2).d|E(T
−
6
)|=11 Υ,3{v
2
,v
3
}†{u
2
,u
3
}¥k3 ^>,Ø”
•v
2
u
2
,v
3
u
2
,v
3
u
2
.©ÛŒ,c(v
2
u
2
)∈{c(wv
3
),c(u
1
u
3
)},c(v
3
u
3
)∈{c(wv
2
),c(u
1
u
2
)}.dž,
{v
2
u
2
,v
3
u
3
,wu
1
}¤˜‡çô3K
2
,†bgñ.
es=2,q=4,|E(G)|≤2×4= 8.dž,·‚S={w
1
,w
2
},V(A
i
) ={v
i
}(i=1,2,3,4)
(•„ã3).©ÛŒ,c(v
1
v
2
)∈{c(w
1
v
3
),c(w
2
v
4
)}.dž,{v
1
v
2
,w
1
v
3
,w
2
v
4
}¤˜‡çô3K
2
,
†bgñ.
ddþ.±y².
½½½nnn3.2.é?¿n≥7,AR(T
−
n
,3K
2
) = n.
y².Äky²e..˜‡ãG∈T
−
n
,§:8•V(G)={v
1
,v
2
,···,v
n
},>8•
E(G)={v
1
v
2
}∪{v
1
v
i
,v
1
v
i
|3≤i≤n}∪{v
i
v
i+1
|3≤i≤n−2}.éuãG,Äkr†v
1
ƒ
n−1^>/þØÓôÚ.éuãG¥•e>,·‚^1n«ôÚ5/.dž,ãG¥vkç
ôkK
2
dd·‚,é?¿n≥7,AR(T
−
n
,3K
2
) ≥n.
éuþ.,·‚^‡y{.b^n+ 1 «ôÚ5/T
−
n
>,džT
−
n
¥Ø¹çô3K
2
.w
,T
−
n
¥kçô2K
2
.-G´T
−
n
çô)¤fã,w,E(G)=n+1.dÚn2.1,•3V(G) 
˜‡f8S,¦o(G−S)−|S|=n−4.-|S|=s,o(G−S)−|S|=q.-G−SÛ©|•
A
1
,A
1
,···,A
q
,-|A
i
|=a
i
(1≤i≤q).Ø”˜„5,·‚a
1
≥a
2
≥···≥a
q
≥1.-G−S
ó©|•C(G) = G−
q
S
i=1
V(A
i
)∪S.duq= s+n−4 …s+q≤n,Ïd0 ≤s≤2.
es=0,q=n−4.a
1
≤3ž,k|E(G)|≤6<n−1,†bgñ.Ïd,C(G)=∅,
a
1
=5,a
2
=a
2
=···=a
q
=1,|E(G)|≤3×5−7=8.¤±,n=7.-V(A
1
)=
{u
1
,u
2
,u
3
,u
4
,u
5
},V(A
2
)={v
2
},V(A
3
)={v
3
}.·‚Œ±3V(A
1
) –•33 ‡:,Ø
”•u
1
,u
2
,u
3
,¦A
1
−u
i
(i=1,2,3)•¹˜‡çôo.dÚn2.2Œv
2
v
3
/∈T
−
7
,=
|E(T
−
7
)|= |E(A
1
)|+|E(A
1
,v
2
)|+|E(A
1
,v
3
)|,|E(A
1
,v
2
)|+|E(A
1
,v
3
)|= |E(T
−
7
)|−|E(A
1
)|= 6.
©ÛŒ,3T
−
7
¥,{v
2
,v
3
}†u
i
(i= 1,2,3)˜½ƒ.Ø”u
1
v
2
∈T
−
7
,®•A
1
−u
1
•¹˜‡
DOI:10.12677/aam.2022.111030241A^êÆ?Ð
{b§u²
çôo,dÚn2.2ŒT
−
7
¥•3˜‡çô3K
2
,†bgñ.
es=1,q=n−3.XJ|C(G)|=2,@o|E(G)|≤n−1 +1=n<n+ 1,†b
gñ.ÏdC(G)=∅,a
1
=3,a
2
=a
2
=···=a
q
=1.-S={w},A
1
={u
1
,u
2
,u
3
},
V(A
i
)={v
i
}(i=2,3,···,n−3),V={v
2
,v
2
,···,v
n−3
}.dA
1
äk Ïf.5Œ A
1
Óu
K
3
…|E(S,V(A
1
)∪V)|=n−2.Ø”˜„5,·‚©wu
1
/∈E(G) ½öwu
n−3
/∈E(G) ü«œ¹
?Ø.dž,wu
2
,wu
3
∈E(G),wv
i
∈E(G)(i=2,3,···,n−4).Xã4,-c(u
1
u
2
)=1,c(u
1
u
3
)=
2,c(u
2
u
3
)=3,c(wu
2
)=4,c(wu
3
)=5,c(wv
2
)=6,c(wv
3
)=7.duG(S∪V(A
1
)) •¹˜‡çô
o,dÚn2.2·‚kE
T
−
n
(V)=∅.duE(A
1
,V)=3n−7−(n+1)=2n−8,=V¥z˜
‡:Ñ–†A
1
¥ü‡:ƒ.Ø”v
2
u
3
,v
3
u
1
∈E(T
−
n
).wu
1
∈E(G),wv
n−3
/∈E(G)
ž,dT
−
n
عçô3K
2
,¤±c(v
2
u
3
) ∈{1,7},c(v
3
u
1
) ∈{3,6}.dž,{v
2
u
3
,v
3
u
1
,wu
2
}´˜‡ç
ô3k
2
,†bgñ.wu
1
/∈E(G),wv
n−3
∈E(G) ž,-c(w v
4
)=8.duT
−
n
عçô3K
2
,
¤±c(v
2
u
3
)∈{1,7}∩{1,8}.Ïd, c(v
2
u
3
)=1.duT
−
n
عçô3K
2
,¤±c(v
3
u
1
)=7.dž,
{v
2
u
3
,v
3
u
1
,wv
4
}´˜‡çô3K
2
,†bgñ.
es=2,q=n−2.dž|C(G)|=∅,a
1
=a
2
=···=a
n−2
=1.-S={w
1
,w
2
},
V(A
i
) = {v
i
}(i= 1,2,···,n−2),V= {v
2
,v
2
,···,v
n−2
}.w
1
w
2
/∈E(G) ž,3V¥–kn‡
:Ý•2.Ø”˜„5,·‚d
G
(v
1
) = d
G
(v
2
) = d
G
(v
3
) = 2.{ü©ÛŒG[w
1
,w
2
,v
i
,v
j
](1 ≤
i,j≤3)•¹˜‡çôo,dÚn2.2ŒE
T
−
n
(V)=∅…E
T
−
n
({v
i
},{v
4
,v
5
,···,v
n−2
})=
∅(i=1,2,3).Ïd,E
T
−
n
≤2(n−2) + 1+ 3=2n≤3n−7,=n=7.džw
1
,w
2
,v
1
,v
2
,v
3
†K
5
Ó,ù†T
−
n
´²¡ãgñ.w
1
w
2
∈E(G)ž,XJ3{v
1
,v
2
,···,v
n−2
}¥–k
n‡:Ý•2.Ø”˜„5,·‚d
G
(v
1
)=d
G
(v
2
)=d
G
(v
3
)=2,dc¡y²Œ±í
Ñgñ.Ïd,3{v
1
,v
2
,···,v
n−2
}¥••3ü‡:Ý•2.Ø”˜„5,·‚d
G
(v
1
)=
d
G
(v
2
)=2,d
G
(v
2
)=d
G
(v
3
)=···=d
G
(v
n−2
)=1.Ø”˜„5,-{w
1
v
3
,w
2
v
4
}⊆E(G).d u
E({w
1
,w
2
},V)=3n−7 −(n+1)=2n−8,=V¥z‡:цduv
1
,v
2
ƒ.{ü©ÛŒ
c(v
2
v
3
) ∈{c(w
1
v
1
),c(w
2
v
4
)},c(v
1
v
4
) ∈{c(w
1
v
3
),c(w
2
v
2
)}.dž, {w
1
w
2
,v
2
v
3
,v
1
v
4
}´˜‡çô
3K
2
,†bgñ.
dd,·‚y²n≥7,AR(T
−
n
,3K
2
) ≤n.
½½½nnn3.3.é?¿n≥8,AR(T
−
n
,4K
2
) = 2n−2.
y².Äky²e..˜‡ãG∈T
−
n
,§:8•V(G)={v
1
,v
2
,···,v
n
},>8•
E(G)= {v
1
v
2
}∪{v
1
v
i
,v
1
v
i
|3 ≤i≤n}∪{v
i
v
i+1
|3 ≤i≤n−2}.éuãG,Äkr¤k †v
1
,v
2
ƒ
2n−3 ^>/þØÓôÚ.éuãG¥•e>,·‚^Ó˜«#ôÚ5/.dž,ãG
¥vkçô4K
2
dd·‚,é?¿n≥8,AR(T
−
n
,4K
2
) ≥2n−2.
éuþ.,·‚^‡y{.b^2n−1«ôÚ5/T
−
n
>,džT
−
n
¥Ø¹çô4K
2
.w,,
T
−
n
¥kçô3K
2
.-G´T
−
n
çô)¤fã,w,,E(G)= 2n−1.dž,G¥¹kçô3K
2
عçô4K
2
.dÚn2.1,•3V(G) ˜‡f8S,¦o(G−S) −|S|=n−6.-|S|=s,
o(G−S)−|S|= q.-G−SÛ©|•A
1
,A
1
,···,A
q
Ù¥|A
i
|= a
i
(1 ≤i≤q).Ø”˜„5,·
‚a
1
≥a
2
≥···≥a
q
≥1.-G−Só©|•C(G)= G−
q
S
i=1
V(A
i
)∪S.duq=s+n−6
…s+q≤n,Ïd0 ≤s≤3.
DOI:10.12677/aam.2022.111030242A^êÆ?Ð
{b§u²
es= 0,q= n−6.a
1
≤5ž,|E(G)|≤3×5−7 = 11 <2n−1,†bgñ.Ïda
1
= 7,
a
2
= a
3
= ···= a
q
= 1.dž|E(G)|≤3×7−7 = 14 <2n−1,†bgñ.
es= 1, q= n−5.a
1
≤3ž,|E(G)|≤n−1+6 = n+5 <2n−1, †bgñ.Ïda
1
= 5,
a
2
= a
3
= ···= a
q
= 1.dž|E
G
(S∪V(A
1
))|≤3×6−7 = 11,|E(G)|≤11+n−6 = n+5 <2n−1,
†bgñ.
es=2,q=n−4.dža
1
≤3,a
2
=a
3
=···=v
q
=1.-S={w
1
,w
2
},A
i
={v
i
}(2≤
i≤q).w,,H=G[{w
1
,w
2
,v
2
,···,v
n−2
}] −E
G
({w
1
,w
2
})´˜‡kn−3‡:ܲ¡
ã.Ïd,|E(H)|≤2(n−3) −4=2n−10,|E
G
(S∪C(G) ∪V(A
1
))|≤3 ×5 −7=8.¤±
|E(G)|≤8+|E(H)|= 2n−2 <2n−1,†bgñ.
es= 3,q= n−3,a
2
= a
3
= ···= v
q
= 1.-S= {w
1
,w
2
,w
3
},V
(
A
i
) = {v
i
}(1 ≤i≤n−3),
V{v
1
,v
2
,···,v
n
}.w,,G−{e|e∈E
G
(S)}]´˜‡kn‡:ܲ¡ã,=|E(G)|≤2n−4+3 =
2n−1.dž,G[S]
∼
=
K
3
,Ø”˜„5,d
G
(v
1
) =d
G
(v
2
) =3,d
G
(v
i
) =2(3 ≤i≤n−3).w,,
v
1
v
2
/∈E(T
−
n
),ÄKT
−
n
(S∪{v
1
,v
2
})
∼
=
K
5
,ù†T
−
n
´²¡ãgñ.d²¡ãعK
3,3
ŒE(T
−
n
)\
E(G) à:Ñ3V¥.·‚*G[w
1
,w
2
,w
3
,v
1
,v
2
,v
i
](3 ≤i≤n−3)•¹˜‡çô8.dÚ
n2.3 ŒE
T
−
n
({v
1
v
2
,···,v
n−3
}) = ∅.¤±|E
T
−
n
({v
1
,v
2
},{v
3
v
4
,···,v
n−3
})|= 3n−7−(2n−1) =
n−6≥2.-a=|E
T
−
n
({v
1
},{v
3
v
4
,···,v
n−3
})|,b=|E
T
−
n
({v
2
},{v
3
v
4
,···,v
n−3
})|.Ø”˜„5,
·‚a≥b.n≥9ž·‚ka≥2.-v
1
v
3
∈T
−
n
, XJc(v
2
w
i
) 6= c(v
1
v
3
)(1 ≤i≤3),@ov
1
v
3
ÚE
G
[w
1
,w
2
,w
3
,v
2
,v
4
,v
5
] ¤˜‡çô4K
2
,†bgñ.XJb≥1,dž•3ü^>,Ø”
•v
1
v
3
,v
2
v
4
,·‚kc(v
1
v
3
)∈{c(v
2
w
1
),c(v
2
w
2
),c(v
2
w
3
)},c(v
2
v
4
)∈{c(v
1
w
1
),c(v
1
w
2
),c(v
1
w
3
)}.
dž,v
1
v
3
,v
2
v
4
ÚE
G
({w
1
,w
2
,w
3
,v
5
})|¤˜‡çô4K
2
,†bgñ.XJb=0,dž
v
1
v
i
∈T
−
n
(3≤i≤n−3).d²¡ãعK
3,3
Œ,•3ü‡:v
i
v
j
(3≤i<j≤5),¦
N
S
(v
i
) 6=N
S
(v
j
).Ø”i=3,j= 4,džG[{v
2
,v
3
,v
4
,w
1
w
2
,w
3
}] •¹˜‡çô8.dÚn2.3
±9v
1
v
5
∈E
T
−
n
ŒT
−
n
k˜‡çô4K
2
,†bgñ.n= 8ž, ·‚ka+b= 2.a= b= 1
ž†n≥9œ¹ƒÓ. a= 2,b= 0ž,Ø”{v
1
v
3
,v
1
v
4
}⊂E(T
−
n
).dud
G
(v
4
) = d
G
(v
5
) = 2,
Ø”˜„5,·‚{v
4
w
1
,v
4
w
2
,v
5
w
1
,v
5
w
2
}⊂E(G),dž{v
4
w
1
,v
5
w
2
,v
2
w
3
,v
1
v
3
}´˜‡çô
4K
2
,†bgñ.
dd,·‚y²é?¿n≥8,AR(T
−
n
,4K
2
) ≤2n−2.
Figure4.wu
1
∈E(G)orwv
n−3
∈E(G)
ã4.wu
1
∈E(G)½wv
n−3
∈E(G)
DOI:10.12677/aam.2022.111030243A^êÆ?Ð
{b§u²
Figure5.k=6,n=13
ã5.k=6,n=13
4.çôkK
2
½½½nnn4.1.é?¿k≥6…n≥3k−7,2n+3k−16 ≤AR(T
−
n
,kK
2
) ≤2n+4k−15.
y².Äky²e..·‚E˜‡ãG∈T
−
n
§:8•V(G)={v
1
,v
2
,···,v
n
}.·‚3
k−4´P
1
= v
2
v
3
···v
k−2
Ä:þEãG.1˜Ú, ·‚3P
1
Ä:þV\˜^>v
1
v
2
, -P
1
þ
z˜‡:Ñ©O†v
1
Úv
2
ƒ,Ù¥v
1
v
3
v
2
´¡.1Ú,3v
1
v
i
v
i+1
,v
2
v
i
v
i+1
(3 ≤i≤k−3)
±9v
1
v
2
v
k−2
SÜ©OV\˜‡:,V\2k−9 :•g•v
k−1
,···,v
3k−11
.-V\:†
þn‡:у,dž·‚˜‡k3k−11‡:²¡n¿©ã.1nÚ,V\˜
^n−3k+ 11´P
2
=v
3k−11
v
3k−10
···v
3k−7
,-P
2
þz˜‡:Ñ©O†v
1
Úv
2
ƒ,Ù¥
v
1
v
3
v
2
v
3k−7
´¡.dd,·‚EÑãG.·‚3ã5¥‰Ñk=6äNE•{.éuãG,
·‚rP
2
´þ¤k>/þôÚ1,•e¤k>/þ2n−3k−17 «ØÓôÚ.dž,ãG¥
عçôkK
2
.dd·‚,é?¿k≥6 …n≥3k−7,AR(T
−
n
,kK
2
) ≥2n+3k−16.
éuþ.,·‚^‡y{.b,•3k≥6…n≥3k−7,¦AR(T
−
n
,kK
2
)≥2n+3k−14.
@o,•3T
−
n
˜‡2n+ 3k−14 >/Ú,¦ãT
−
n
عçôkK
2
.-G´T
−
n
çô)¤
fã,w,E(G)=2n+ 3k−14.dž,G¥¹kçô(k−1)K
2
عçôkK
2
.-M=
{u
i
w
i
∈E(G):1≤i≤k−1}´G¥çô(k−1)K
2
.-V(M)={u
1
,···,u
k−1
,w
1
,···,w
k−1
},
R=V(G) \V(M).éui∈[k−1],·‚Ø”b|N
G
(u
i
) ∩R|≤|N
G
(w
i
) ∩R|.duãG¥
•Œšê•k−1,·‚Œ±G[R ]=∅…w
i
žv
i
(1≥i≥k−1)3R¥vkú
:.é?¿i∈[k−1],|N
G
(u
i
) ∩R|=0k|N
G
(w
i
) ∩R|≥0,|N
G
(u
i
) ∩R|=1žk
N
G
(u
i
)∩R= N
G
(w
i
)∩R.·‚Ø”,1 ≤i≤lž,k|N
G
(u
i
)∩R|= 1.l+1≤i≤k−1
ž,k|N
G
(u
i
)∩R|= 0.·‚k|E
G
({u
1
,···,u
l
,w
1
,···,w
l
},R)|= 2l.-L= {w
l+1
,···w
t−1
}.
l= k−1ž,k|E
G
(L,R)|= 0.l≤k−2ž, kE
G
(L,R) ≤2(n−(k−1)−l)−4 = 2n−2k−2l−2.
d|E
G
(M)|≤3(2k−2)−7 = 6k−13,|E(G)|= |E
G
(M)|+|E
G
({u
1
,···,u
l
,w
1
,···,w
l
},R)|+
DOI:10.12677/aam.2022.111030244A^êÆ?Ð
{b§u²
|E
G
(L,R)|≤(6k−12)+2l+(2n−2k−2l−2) = 2n+4k−15,ù†·‚bgñ.dd·‚
,é?¿k≥6 …n≥3k−7,AR(T
−
n
,kK
2
) ≤2n+4k−15.
ë•©z
[1]Erd˝os, P.,Simonovits,M.andS´os,V.T.(1973)Anti-RamseyTheorems.Colloquia Mathematica
SocietatisJ´anosBolyai,10,657-665.
[2]Li,X.L. and Xu, Z.X. (2009) The Rainbow Number of Matchings in Regular Bipartite Graphs.
AppliedMathematicsLetters,22,1525-1528.
https://doi.org/10.1016/j.aml.2009.03.019
[3]Schiermeyer,I. (2004) RainbowNumbers for Matchings and Complete Graphs. DiscreteMath-
ematics,286,157-162.
[4]Jendrol
0
,S.,Schiermeyer,I.andTu,J.H.(2014)RainbowNumbersforMatchingsinPlane
Triangulations.DiscreteMathematics,331,158-164.
https://doi.org/10.1016/j.disc.2014.05.012
[5]Qin,Z.M.,Lan,Y.X.,Shi,Y.T. andYue,J.(2021)Exact Rainbow Numbersfor Matchingsin
PlaneTriangulations.DiscreteMathematics,344,ArticleID:112301.
https://doi.org/10.1016/j.disc.2021.112301
DOI:10.12677/aam.2022.111030245A^êÆ?Ð

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