边着色完全图中的单色圈和单色树

• 作者: 程书婷 吴宝音都仍
• 来源期刊: 新疆大学学报（自然科学版）（中英文）
• 学科: 数学
• 关键词: 周长 边着色完全图 单色圈 单色树
• 年，卷（期）: 2022,（1）
• 所属期刊栏目: 研究精粹|Research Headlines
• 页码范围: 16-18,41
• 页数: 4页
• 分类号: O157
• 语种: 中文
• DOI: 10.13568/j.cnki.651094.651316.2021.12.08.0001

摘要

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