两类平面图的关联色数

轮Wr+1(r≥3)是一个r阶圈加上一个新的顶点,再把圈上每个顶点与新顶点连上边所得到的图.新顶点与圈上顶点之间的边称为辐边,圈上的边称为边缘边.所谓花图Fr,m,n(r≥3,m≥1,n≥2m+1),是在轮Wr+1中的在每条辐边上分别嵌入m-1个新点,在每条边缘边上分别嵌入n-2m-1个新点所得到的图.所谓棱柱Qn(n≥3),是指Qn=(V,E),V={u1,u2,…,un}∪{v1,v2,…,vn},E={uiui+1,vivi+1,uivi,uivi+1|i=1,2,…,n},其中un+1=u1,vn+1=v1.通过给出花图Fr,m,n(r≥3,m≥1,n≥2m+1)和棱柱Qn(n≥3)的一种关联着色方法,确定了它们的关联色数.

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

设Kn是具有n个顶点的完全图,f(n)是满足下列条件的最小正整数:对于任意的正整数m≥f(n),存在Kn的一个m边着色,使得Kn中的任一个K4至少含5种颜色.Erdos和Gyaras给出了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.

花图的邻点可区别关联色数

轮Wr+1(r≥3)是一个r阶圈加上一个新的顶点,再把圈上每个顶点与新顶点连上边所得到的图,新顶点与圈上顶点之间的边称为辐边,圈上的边称为边缘边。所谓花图Fr,m,n(r≥3,m≥1,n≥2m+1)是在轮Wr+1中,在每条辐边上分别嵌入m-1个新点,在每条边缘边上分别嵌入n-2m-1个新点所得到的图。研究花图Fr,m,n(r≥3,m≥1,n≥2m+1)的邻点可区别关联着色,确定了部分花图的邻点可区别关联色数,并给出了剩余花图的邻点可区别关联色数的上界。

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

设K_n是具有n个顶点的完全图,f(n)是满足下列条件的最小正整数:对于任意的正整数m≥f(n),存在K_n的一个m边着色,使得K_n中的任一个K-4至少含5种颜色。Erdos和Gyarfas给出了f(n)的上下界:2/3n<f(n)<n;并且证明了f(9)=8.作者证明了f(10)=9;并且改进了f(n)的下界:f(n)>2/3n+1.

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

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

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

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

花图F_(r.m.n)的邻点可区别全染色

设G是阶数不小于3的简单连通图,G的k-正常全染f色称为是邻点可区别的,如果对G的任意相邻的两顶点,其点的颜色及关联边的颜色构成的集合不同。这样的k中最小者称为是G的邻点可区别全色数。得到了花图的邻点可区别全色数。