5色K4问题的推广  

A generalization of the five-color K4 problem

作　　者：方影[1] 孙庆文[1] 黄平[1] 

机构地区：[1]第二军医大学数理教研室

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

基　　金：第二军医大学校优秀课程《高等教学》立项项目

摘　　要：设Kn是具有n个顶点的完全图,fr（n）是满足下列条件的最小正整数：对于任意的正整数m≥fr（n）,存在Kn的一个m边着色,使得Kn中的任一个Kr至少含r（r-1）/2-1种颜色.确定fr（n）的问题称为n阶完全图的r（r-1）/2-1色Kr问题（4≤r≤n）.给出了f5（n）的上界.关于14色K6问题的充要条件和f6（n）的下界.同时证明了f6（7）=19,f6（8）=26,f6（9）=33;f7（n）=n（n-1）/2-[n/4];fr（n）=n（n-1）/2-1（8≤r≤n）.Let Kn be the complete graph with n vertices,and fr（n）be the smallest positive integer satisfying the following condition：for any positive integer m≥fr（n）,there is a proper m-edge coloring of Kn,such that every Kr in Kn gets at least r（r-1）/2-1 colors.The problem of determining fr（n）is called the r（r-1）/2-1 color Kr problem of the complete graph with n vertices（4≤r≤n）.We give the supper bound of f5（n）,and give the necessarily and sufficient condition about the fourteen-color K6 problem and the lower bound for f6（n）.Furthermore,we prove that f6（7）=19,f6（8）=26,f6（9）=33;f7（n）=n（n-1）2-[n/4];fr（n）=n（n-1）2-1（8≤r≤n）.

关 键 词：边着色 对集 5色K4条件 

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