满足5色K_4条件完全图的边着色  

The Edge Coloring of the Complete Graph Satisfying the Five-Color K_4 Condition

作　　者：唐明元[1] 

机构地区：[1]上海师范大学数理信息学院,上海200234

出　　处：《上海师范大学学报（自然科学版）》2003年第3期21-25,共5页Journal of Shanghai Normal University(Natural Sciences)

基　　金：上海市教委科技发展基金(02DK06)

摘　　要：设K_n是具有n个顶点的完全图,f(n)是满足下列条件的最小正整数:对于任意的正整数m≥f(n),存在K_n的一个m边着色,使得K_n中的任一个K-4至少含5种颜色。Erdos和Gyarfas给出了f(n)的上下界:2/3n<f(n)<n;并且证明了f(9)=8.作者证明了f(10)=9;并且改进了f(n)的下界:f(n)>2/3n+1.Let Ka be a 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 . Erdos and Gyarfas gave the upper-lower bound of f(n): -2/3n<f(n) < n; and provedf(9) = 8. In this paper , we prove f( 10) =9, and improve the lower bound of f(n): f(n)>2/3n+1.

关 键 词：花形图 正规花形图 5色K4条件 

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