关于5色K_4问题的两个充要条件  

Two necessary and sufficient conditions for the five-color K_4 problem

作　　者：方影[1] 秦超[2] 孙庆文[1] 

机构地区：[1]第二军医大学数理教研室,上海200433 [2]第二军医大学卫勤教研室,上海200433

出　　处：《上海师范大学学报（自然科学版）》2007年第4期30-33,共4页Journal of Shanghai Normal University(Natural Sciences)

摘　　要：设K_n是具有n个顶点的完全图,f(n)是满足下列条件的最小正整数:对于任意的正整数m≥f(n),存在K_n的一个m边着色,使得K_n中的任一个K_4至少含5种颜色.Erd(?)s和Gy(?)rf(?)s给出了f(n)的上下界:2/3n<f(n)<n;并且证明了f(9)=8.唐明元证明了f(10) =9;并且改进了f(n)的下界:f(n)>2/3n+1.作者进一步改进了f(n)的下界:当n≥20时,f(n)>1/8(6n-5).给出了关于5色K_4问题的两个充要条件.Let Kn be the complete graph with n vertices , f（n） the smallest positive integer satisfying the following condition ： For any positive integer m ≥ f（n） , there is an m - edge coloring of Kn, such that every K4 in Kn gets at least 5 colors . Erdoes and Gyarfas gave the upperlower bound off（n） ： 2/3n〈f（n）〈n ; and proved f（9） = 8. Tang ming-yuan proved f（10） =9 ; and improved the lower bound of f（n） ： f（n）〉2/3n＋1, We proved f（ 11 ） = 10 ; and improved the lower bound of f（n）again： f（n）〉1/8（6n-5） ,（n ≥ 20）. In this paper, two necessarily and sufficient condition for the five-color K4 problem is given.

关 键 词：5色K4条件 4色H4条件 3色C4条件 

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