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

Monochromatic Cycles and Trees in Edge-Colored Complete Graphs

作　　者：程书婷 吴宝音都仍 CHENG Shuting;WU Baoyindureng(School of Mathematics and System Sciences,Xinjiang University,Urumqi Xinjiang 830017,China)

机构地区：[1]新疆大学数学与系统科学学院,新疆乌鲁木齐830017

出　　处：《新疆大学学报（自然科学版）（中英文）》2022年第1期16-18,41,共4页Journal of Xinjiang University(Natural Science Edition in Chinese and English)

基　　金：supported by National Natural Science Foundation of People’s Republic of China(12061073).

摘　　要：令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.Let f(r,n)be the maximum integer k such that every r-edge-colored complete graph K_(n) contains a monochromatic cycle of length at least k.In 2009,Faudree,Lesniak and Schiermeyer conjectured that every(r+1)-edge-colored complete graph K_(n) contains a monochromatic cycle of length at least n/r for r≥2.Meanwhile,they also proved that f(2,n)≥[2n/3]for n≥6,and this bound is sharp.In 2011,Fujita disproved this conjecture for n=2 r and also showed that every r-edge-colored complete graph K_(n) contains a monochromatic cycle of length at least n/r for 1≤r≤n.In this paper,we disprove this conjecture for n=rt+1,where r≥2 and n-1/r is a positive even integer.More precisely,there exists a(r+1)-edge-colored complete graph K_(n) contains a monochromatic cycle of length less than n/r.For a k-edge coloring c of K_(n),let moc(K_(n),c)be the largest order of monochromatic tree of K_(n) under c.Let moc(n,k)=min{moc(K_(n),c):c is a k-edge coloring of K_(n)}.We show that for any positive integer n≥3,moc(n,3)=[n/2]if n≡0,1(mod 4)and moc(n,3)=[n+1/2]if n≡2,3(mod 4).

关 键 词：周长 边着色完全图 单色圈 单色树 

分 类 号：O157[理学—数学]