关于C_mo C_n和C_mo P_n星全色数

对于一个图G=G(V(G),E(G)),用V(G)和E(G)表示图的顶点集合和边集合.图G的3个顶点的路边和顶点着有5种色,跑遍图G的所有k星全着色所取得的最小数k称为图G的星全色数,简记为sχt(G).主要研究了Cmo Cn和Cmo Pn2种冠图的星全染色规律,并得出它们的星全色数.

若干图广义字典积的星全色数

设G是具有顶点集C(G)={t_0,…t_(n-1)}(n≥2)的图,h_n=(H_i)_(i∈(0,1,…n-1))是不相交图的序列,其中H_i的顶点集为V(H_i)={(t_i,y_i),…,(t_i,y_i)},x≥1.称G[h_n]为G与h_n=(H_i)_(i∈(0,1.…n-1))的广义字典积,其中G[h_n]的顶点集为V(G[h_n])=U^(n-1)_(i-0)V(H_i),且两个顶点(t_i,y_p)与(t_j,y_q)相邻当且仅当t_i=t_j且(t_i,y_p)(t_i,y_q)∈E(H_i)或(t_i,t_j)∈E(G).关于G与h_n=(H_i)_(i∈{0,1.…n-1})的广义字典积G[h_n]的星全色数,我们得到了文中的两个重要结果.

关于图D(Cn),Cn^2,Cn^3的星全色数

图G的一个k-全着色满足G的任何路长为2的点,边着色均不相同,我们称它为G的k-星全着色.图G的全部k-星全着色中最小的k称为图G的星全色数,记为χst(G).讨论一些圈的星全染色问题,得到了图D(Cn)(n=0(mod 3)和n=0(mod 5)),C2n(n=0(mod 20)和n=0(mod 28))以及C3n(n=0(mod 28)和n=0(mod 36))的星全色数.

最大度不小于3的图的星全色数的一个上界

对圈、扇和轮作了简单的剖分，得到了其剖分图的星全色数，并运用Lovasz局部引理证明了若G（KE）是一个最大度为△≥3的简单无向图，则Xst（G）≤22△^2．

轮和路的广义Mycielski图的星全染色

图G的一个正常全染色被称作G的星全染色,如果G中任意路长为2的点和边着色均不相同.图的全部星k-全着色中最小的数k称为它的星全色数.讨论轮和路的广义Mycielski图的星全染色问题,得到不同情况下它们的星全色数,其中每个点的色集合包含该点及其关联边的颜色.

若干合成图的星全染色

简单图G和H的合成图是指具有顶点集V(G)×V(H)的简单图G[H],它的顶点(u,v)和另一个顶点(u′,v′)相邻当且仅当或者uu′∈E(G),或者u=u′且vv′∈E(H).文中研究了n+1阶简单图G与m阶简单图H的合成图的星全染色,其中G为轮Wn,扇Fn,或星Sn.得到以下结果:(1)若Δ(H)=2且n≥4,m≥5,则G[H]的星全色数为(2n+1)m;(2)若χ′(H)=Δ(H)=m-1且n,m≥4,则G[H]的星全色数为2(n+1)m-1.

若干笛卡尔积图的星全染色

图G的一个正常全染色如果满足G中任意路长为2的点和边着色均不相同时,称为G的星全染色.图的全部k-星全染色中所用最少的颜色数称为图G的星全色数.得到了路与星、轮、扇的笛卡尔积图的星全色数.

若干联图的星全染色

图G的一个正常全染色如果满足G中任意路长为2的点和边着色均不相同,称为G的星全染色.图的全部k-星全染色中所用最少的颜色数称为图G的星全色数.文章研究了若干联图的星全色数.

若干特殊图的广义字典积的星全染色

设G是具有顶点集V(G)={t0,…,tn-1}(n≥2)的图,h n=(Hi)i∈{0,1,…,n-1}是不相交图的序列,其中H i的顶点集为V(Hi)={(ti,y1),…,(ti,yx)},x≥1。文中用构造染色集的方法,研究得到了若干特殊图的广义字典积G[h n]的星全色数。

完全图和完全多部图的Mycielski图的星全染色

讨论了完全二部图、完全图和完全多部图的Mycielski图的星全染色问题,得到了它的星全色数.

等广义联图的Mycielski图的星全染色(英文)

研究了一些等广义联图的Mycielski图的星全染色,并得到了它们的星全色数。

一类字典积C_n[H]的星全染色

简单图G和H的字典积G[H]是指具有顶点集V(G)×V(H)的简单图G[H],其顶点(u,v)和另一个顶点(u',v')相邻当且仅当uu'∈E(G),或者u=u'且vv'∈E(H).研究了n阶圈Cn与m阶简单图H的字典积Cn[H]的星全染色,得到了圈与某些特殊图的字典积的星全色数.