5色K4问题与正常边着色

• 作 者: 方影 孙庆文
• 机 构: 第二军医大学数理教研室
• 出 处: 上海师范大学学报：自然科学版
• 发表日期: 2009年4期
• 关键词: 正常边着色 5色K4条件 9色K5条件 proper edge coloring five-color K4 condition nine-color K5
• 基金项目: 第二军医大学校基金（JYL2009042）.

设Kn是具有n个顶点的完全图，k（n）是满足下列条件的最小正整数：对于任意的正整数m≥k（n），存在Kn的一个正常m边着色，使得Kn中的任一个K4至少含5种颜色,f5（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．