5色K4问题与正常边着色

设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.     

关于5色K4问题的两个充要条件

设KN是具有n个顶点的完全图,f（n）是满足下列条件的最小正整数：对于任意的正整数m≥f（n）,存在Kn的一个m边着色,使得Kn中的任一个巧至少含5种颜色．Erdoes和Gyarfas给出了f（n）的上下界：2/3n〈f（n）〈n;并且证明了f（9）=8．唐明元证明了f（10）=9;并且改进了f（n）的下界：f（n）〉2/3n＋1．作者进一步改进了f（n）的下界：当n≥20时,f（n）〉1/8（6n-5）．给出了关于5色K4问题的两个充要条件．     

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

设p(n)是满足下列条件的最小正整数:对于任意大于或等于p(n)的正整数m,在n个顶点的完全图中有一个m边着色,使得其中的任一条长为4的路P4至少含2种颜色.通过对n个顶点的完全图构造新的边着色,得到了2色P4问题的新的上界:2n-3[log3 n]-12(n大于8), 并且对于大于或等于2的正整数k,给出了p(3k-2)与p(3k-1)以及p(3k)的值为3k-12;p(3k+1)的值为3k+12;p(3k+2)的值为3k+32.所得到的结果推广和改进了近期的相关结果.     

关于n阶完全图的5色K4问题

设Kn是具有n个顶点的完全图,f(n)是满足下列条件的最小正整数对于任意的正整数m≥f(n),存在Kn的一个m边着色,使得K中的任一个K4至少含5种颜色.Erdos和Gyárás给出了f(n)的上下界2/3n＜f(n)＜n;并且证明了f(9)=8.唐在[3]中证明了f(10)=9;并且改进了f(n)的下界f(n)＞2/3n+1.作者进一步改进了f(n)的下界当n≥20时,f(n)＞1/8(6n-5),同时证明了f(11)=10.     

关于5色K4问题的两个新的结果

设Kn是具有n个顶点的完全图,f(n)是满足下列条件的最小正整数对于任意的正整数m≥(fn),存在Kn的一个m边着色,使得Kn中的任一个K4至少含5种颜色.Erd(o)s和Gyárfás给出了f(n)的上下界2/3n＜f(n)＜n;并且证明了f(9)=8.唐明元曾经证明了f(10)=9.作者曾经证明了f(11)=10,在此文中作者又进一步证明了f(12)=11,f(13)=12.     

满足5色K4条件完全图的边着色

设K_n是具有n个顶点的完全图,f(n)是满足下列条件的最小正整数:对于任意的正整数m≥f(n),存在K_n的一个m边着色,使得K_n中的任一个K-4至少含5种颜色。Erdos和Gyarfas给出了f(n)的上下界:2/3n2/3n 1.     

一类色唯一的K_1-同胚图

令K4(i,j,k,l,m,n)表示图G的色多项式,如果P(G)=P(H),称G和H色等价;如果对任意图H,当P(H=P(G))时,都有H和G同构,称G是色唯一的.令K4(i,j,k,l,m,n)表示两两三度点间的路长分别为i,j,k,l,m,n的K4-同胚图.作者对集合{i,j,k,l,m,n}由3个不同值组成,且等于每个值的路都恰有2条的K4-同胚图的着色进行了研究,得到了1类色唯一的K4-同胚图.     

一类色唯一的K_4同胚图

本文证得 :如果正整数x ,y,z ,u ,v ,w中有四个数等于a(≥ 2 ) ,而另外两个数均小于a或其中一个大于a、另一个小于a ,则k4 (x ,y ,z ,u ,v ,w)是色唯一的。     

关于K_4(1,3,3,δ,ε,η)的同类色等价类

本文给出了K4-同胚图K4(1,3,3,δ,ε,η)的所有同类色等价类,从而刻划了K4(1,3,3,δ,ε,η)的结构特征.     

关于两类K_4同胚图色等价性的研究

利用色多项式研究了围长为7的K4同胚图K4(1,3,3,δ,ε,η)与K4(3,2,2,δ',ε',η')之间的色等价性问题,指出围长为7的K4同胚图K4(1,3,3,δ,ε,η)与K4(3,2,2,δ',ε',η')不存在色等价关系。这一结论有助于解决围长为7的K同胚图的色唯一性问题。