CIRCULAR CHROMATIC NUMBER AND MYCIELSKI GRAPHS

For a general graph G, M（G） denotes its Mycielski graph. This article gives a number of new sufficient conditions for G to have the circular chromatic number xc（M（G）） equals to the chromatic number x（M（G））, which have improved some best sufficient conditions published up to date.

关于Mycielski图补图的一些指标的结果

拓扑指标是分子结构的数学描述符,它将分子的形状、大小、分支等结构特征数值化,且计算简便、取值客观,不易受经验和实验的影响,是数学与化学研究中非常活跃的领域之一。研究拓扑指标图不变量可用于描述和预测有机化合物的理化或药理性质。文章研究Mycielski图的补图的两类度距离指标:Schultz指标和修正的Schultz指标。同时,还给出了一些特殊图的Mycielski图及其补图的Lanzhou指标的表达式。

广义Mycielski图M_(n)(C_(m)^(3))的邻和可区别全染色

将阶数至少为4的圈图中距离为3的任意两点连边得到了圈的3次方图,应用构造染色法,研究了广义Mycielski图M_(n)(C_(m)^(3))和M n(C k 2k)的邻和可区别全染色问题,得到了邻和可区别全色数,验证了邻和可区别全色数的猜想对这两类图的正确性.

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

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

星图和扇图的广义Mycielski图的星全染色

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

完全图的广义Mycielski图的邻点可区别的全色数

对图 G 的一个 k-正常全染色法,若满足相邻点的点染色和关联边的色集合不同时,称该染色法为邻点可区别全染色,其所用小染色数 k 称为 G 的邻点可区别全色数．得到了完全图 K_m 的广义 Mycieski 图 M_n(K_m)(n≥1,m≥3)的邻点可区别全色数．

多重Mycielski图的邻点可区别全染色

给出了一个简单图G的k重Mycielski图Mk(G)(其中k为正整数)的邻点可区别全色数的上界,得到了圈、星、轮、扇的k重Mycielski图的邻点可区别全色数.

关于几类特殊图的Mycielski图的点可区别全色数

讨论并得到了路、圈、完全图、星、扇、轮的Mycielski图的点可区别全色数.

关于图的广义Mycielski图的邻点可区别关联着色

邻点可区别关联着色是使得相邻顶点的颜色集不同的关联着色。主要研究了路,圈C3m,C4m与完全图的广义Mycielski图的邻点可区别关联色数,拓展了图着色的领域,便于更好的研究图的结构。

路的广义Mycielski图的邻点可区别的全染色

图G的一个正常全染色称为G的邻点可区别的全染色,如果对于G中任意相邻的点u和v有C(u)≠C(v).研究图的邻点可区别的全染色就是找出图的邻点可区别全染色的最小色数.利用穷举法和组合分析法研究路的广义Mycielski图的邻点可区别的全染色,得到路的广义Mycielski图的邻点可区别的全色数.

多重Mycielski图的点可区别全染色

给出了最小度至少是2的图G的k重Mycielski图M^k(G)(其中k为正整数)的点可区别全色数的上界.

若干Mycielski图邻点可区别Ⅰ-均匀全染色

图G的一个邻点可区别Ⅰ-均匀全染色是指对图G的邻点可区别的一个Ⅰ-全染色f,若f还满足||T_i|-|T_j||≤1(i≠j),其中T_i=V_i∪E_i={v|v∈V(G),f(v)=i}∪{e|e∈E(G),f(e)=i},则称f为图G的一个邻点可区别Ⅰ-均匀全染色,而图G的邻点可区别Ⅰ-均匀全染色中所用的最少颜色数称为图G的邻点可区别Ⅰ-均匀全色数.通过函数构造法,得到了M(Pn)、M(Cn)、M(Sn)的邻点可区别Ⅰ-均匀全色数,并且满足猜想.

一些图的Mycielski图的均匀邻强边染色

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数目相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数.本文得到了路、圈、星和扇的Mycielski图的均匀邻强边色数.

Mycielski图的对策染色数

介绍了一种新的图着色——关于图 G的对策色数 和对策色数χ*g ( G) .确定了 Mycielski图的对策色数 ,并给出了选手 A获胜的对策 .讨论了关于对策染色

关于S_m广义Mycielski图的若干色性

对图G(V,E),Mn(G)称为G的广义Mycielski图,其中V(Mn(G))={v00,v01,v02,…,v0m;v10,v11,v12,…,v1m;…;vn0,vn1,…,vnm};E(Mn(G))=E(G)∪{vi jv(i+1)k|v0jv0k∈E(G),0≤j,k≤m,i=0,1,…,n-1},m+1阶星Sm的广义Mycielski图,记为Mn(Sm),给出了Mn(Sm)的点色数,边色数,邻强边色数,全色数,邻点可区别的全色数.

广义Mycielski图的邻点可约边染色

对简单图G(V,E),若存在自然数k(1≤k≤Δ(G))和映射f∶E(G)→{1,2,…,k}使得对任意相邻两点u,v∈V(G),uv∈E(G),当d(u)=d(v)时,有C(u)=C(v),则f为G的k-邻点可约边染色,其所用最多染色数称为图G的邻点可约边色数,本文得到了若干广义Mycielski图的邻点可约边染色数.

完全二部图的Mycielski图的点可区别全色数

图的一个正常的全染色如果满足不同点的点及其关联边的色集合不同,则称该染色法为点可区别全染色,其所用最少颜色数称为该图的点可区别全色数.给出了完全二部图的Mycielski图的点可区别全色数.

关于完全图的Mycielski图的循环色数的若干结果

给出了任意图 G的多重 Mycielski图 Mm (G)的简单定义方式 ,用不同的方法证明了当完全图 Kn 的阶数 n足够大时 ,Mm(Kn)的循环色数等于其点色数 .特别证明了 ,n =7,8,9时 ,M3 (Kn)的循环色数等于其点色数 ,从而使得“当 n m +2 ,有χc(Mm(Kn) ) =χ(Mm(Kn) ) =m +n成立”的猜想有了更新的进展 .

两类圈的广义Mycielski图的邻强边色数

设G是简单图,V(Mn(G))={v01,v02,…,v0p;v11,v12,…,v1p;…;vn1,vn2,…,vnp};E(Mn(G))=E(G)∪{vijv(i+1)k|v0jv0k∈E(G),1≤i,j≤p,i=0,1,…,n-1},则Mn(G)称为G的广义Mycielski图,其中,V(G)={v0i|i=1,2,…,p}.本文得到了Mn(Cm)的邻强边色数,其中,Cm是m阶圈,且m≡0(mod 5)或m≡0(mod 6).

若干Mycielski图的邻点可区别均匀全染色

如果图G的一个正常全染色满足相邻点的色集合不同,且任意两种颜色所染的元素的数目之差的绝对值不超过1,则称为邻点可区别均匀全染色(AVDETC),其所用的最少颜色数称为邻点可区别均匀全色数。本文研究了路、圈、星、扇的Mycielski图的邻点可区别均匀全染色,利用构造法和匹配法给出了它们的邻点可区别全色数的确切值,验证了它们满足邻点可区别均匀全染色猜想(AVDETCC)。