满足2色P_4条件完全图的边着色  

The edge coloring of complete graph satisfying the two-color P_4

作　　者：唐明元[1] 

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

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

摘　　要：设Kn是具有n个顶点的完全图,p(n)是满足下列条件的最小正整数,对于任意的正整数m≥p(n),存在Kn的一个m边着色,使得Kn中的任一个P4至少含2种颜色.给出了n阶完全图的2色P4问题的充要条件和p(n)的上下界:p(n)的上界为n-1,它的下界为12n.并且证明了p(6)=p(7)=p(8)=p(9)=4.Let K~ be the complete graph with n vertices , andp（n） be the smallest positive integer satisfying the following condition ： for any positive integer m ≥ p（n） , there is a m- edge coloring ofKn such that every P4 in Kn gets at least 2 colors. In this paper , we give the necessary and sufficient condition for the two-color P4 problem and the upper-lower bound of p（n） ： the upper bound ofp（n） is n - 1, and lower bound is [n/2]. Furthermore, we prove thatp（6） = p（7） = p（8） = p（9） = 4.

关 键 词：2色P4条件 n色花形图 边色矩阵 

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