5色K_4问题与正常边着色

作     者：方影 孙庆文 FANG Ying,SUN Qing-Wen(Mathematics and physics department,Second Military Medical University,Shanghai 200433,China)

作者机构：第二军医大学数理教研室上海200433 

出 版 物：《上海师范大学学报（自然科学版）》 (Journal of Shanghai Normal University(Natural Sciences))

年 卷 期：2009年第38卷第4期

页      面：372-375页

学科分类：07[理学] 070104[理学-应用数学] 0701[理学-数学] 

基　　金：第二军医大学校基金(JYL2009042) 

主　　题：正常边着色 5色K4条件 9色K5条件 

摘      要：设Kn是具有n个顶点的完全图,k(n)是满足下列条件的最小正整数:对于任意的正整数m≥k(n),存在Kn的一个正常m边着色,使得Kn中的任一个K4至少含5种颜色.5f(n)是满足下列条件的最小正整数:对于任意的正整数m≥f5(n),存在Kn的一个m边着色,使得Kn中的任一个K5至少含9种颜色.确定f5(n)的问题称为9色K5问题.给出了关于9色K5问题的充要条件和f5(n)的下界,同时证明了当n是偶数时,并且(n-1)不是3的整数倍,则k(n)=n-1;当n是奇数时,并且n不是3的整数倍,则k(n)=n.