关于2色P_4问题的一些新的结果  

Some new conclusions on the two-color P_4 problem

作　　者：唐明元[1] 

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

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

摘　　要：设p(n)是满足下列条件的最小正整数:对于任意大于或等于p(n)的正整数m,在n个顶点的完全图中有一个m边着色,使得其中的任一条长为4的路P4至少含2种颜色.通过对n个顶点的完全图构造新的边着色,得到了2色P4问题的新的上界:(2n-3[log3n]-1)/2(n大于8).并且对于大于或等于2的正整数k,给出了p(3k-2)与p(3k-1)以及p(3k)的值为(3k-1)/2;p(3k+1)的值为(3k+1)/2;p(3k+2)的值为(3k+3)/2.所得到的结果推广和改进了近期的相关结果.Let p（n） be the smallest positive integer satisfying the following condition：For any positive integer mno less than p（n）,there is a m-edge coloring of the complete graph with n vertices,such that every walk P4 with the length four in the complete graph gets at least two colors.By constrcuting new edge coloring for the complete graph with n vertices,we obtain the new upper bound of two-color P4 problem：（2n-3[log3n]-1）/2 （n more than 8）,and give the following value：the value of p（3k-2）and p（3k-1）and p（3k）are （3k-1）/2;the value of p（3k＋1） are （3k＋1）/2;the value of p（3k＋2） are （3k＋3）/2 for kno less two.Ohr main results extend and generlize some releted known results.

关 键 词：2色P4条件 2色P4问题 边着色 

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