边着色完全图中的单色圈和单色树(英文)

程书婷, 吴宝音都仍

新疆大学学报(自然科学版中英文) ›› 2022, Vol. 39 ›› Issue (01) : 16-18+41. DOI: 10.13568/j.cnki.651094.651316.2021.12.08.0001

边着色完全图中的单色圈和单色树(英文)

  • 程书婷, 吴宝音都仍
作者信息 +
History +

摘要

令f(r,n)是使得任意r-边着色完全图K_n包含一个长度至少为k的单色圈的最大正整数k. 2009年,Faudree,Lesniak和Schiermeyer提出猜想:任意(r+1)-边着色完全图K_n包含一个长度至少为n/r的单色圈,其中r≥2.同时他们还证明了f(2,n)≥[2n/3]且界是紧的,其中n≥6.2011年,Fujita证明了当n=2r时猜想不成立,同时还证明了任意r-边着色完全图K_n包含一个长度至少为n/r的单色圈,其中1≤r≤n.本文中我们证明了存在(r+1)-边着色完全图K_n包含一个长度小于n/r的单色圈,其中n=tr+1,r≥2且n-1/r为正偶数.令c表示K_n的某种k-边着色.在边着色c的完全图K_n中,令moc(K_n,c)表示单色树的最大阶数且moc(n,k)=min{moc(K_n,c):c是K_n的某种k-边着色}.我们还证明了当n≡0, 1 (mod 4)时,moc(n, 3)=[n/2];当n≡2,3 (mod 4)时,moc(n,3)=[n+1/2],其中n≥3.

关键词

周长 / 边着色完全图 / 单色圈 / 单色树

中图分类号

O157.5

引用本文

导出引用
程书婷, 吴宝音都仍. 边着色完全图中的单色圈和单色树(英文). 新疆大学学报(自然科学版中英文). 2022, 39(01): 16-18+41 https://doi.org/10.13568/j.cnki.651094.651316.2021.12.08.0001

基金

supported by National Natural Science Foundation of People’s Republic of China(12061073)

评论

Accesses

Citation

Detail

段落导航
相关文章

/