边着色完全图中的单色圈和单色树（英文）

摘要

令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.

关键词

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