乘积图的分数染色

文中通过讨论由Hamilton圈、二部图、Ga、等图构造的Cartesian乘积图的分数染色，初步研究了Cartesian乘积图分数染色的一般规律．     

完全二部图K_(5,7)点强可区别全染色方案探讨

利用组合分析的方法先讨论了完全二部图K_(5,7)的点强可区别全染色,在此基础之上给出了两种具体的关于完全二部图K_(5,7)的点强可区别全染色方案.此结果的给出不仅确定了完全二部图K5,7的点强可区别全色数为9,而且对于胡志涛所提出的关于完全二部图的点强可区别全染色的猜想:"如果m≥4且n2 m-2时,那么χvst(Km,n)=n+3"中当m=5时作出了否定,从而进一步确定了此猜想成立的范围.     

几类特殊图的邻点可区别全染色

图的邻点可区别全染色,相对于图的正常全染色有更强的要求,因为它要求相邻顶点具有不同的颜色集合.本文刻画了两类特殊的完全多部图、广义圈和广义Mycielski图的邻点可区别全色数.     

完全二部图K11,n(11≤n≤88)的点可区别E-全染色

设图G是简单图,如果给图G中相邻的2个顶点染有不同的颜色,并且让这2个顶点的每条关联边和关联边的端点染不相同颜色的一个全染色称为图G的一个全染色f.如果满足条件对?u,v∈V(G),u≠v,存在C(u)≠C(v),那么f叫做图G的一个E-全染色,简称为VDET染色.文章利用反证法和分析法,讨论完全二部图K11,n(11...     

K3,5,p的点可区别的一般全染色

首先, 利用色集合事先分配法, 反证探讨完全三部图K_3,5,p(p≥5)的点可区别一般全色数, 给出当p较小时的特殊性证明以及当p逐渐增大时的规律性证明； 其次, 利用构造染色法对完全三部图K_3,5,p进行染色, 给出染色方案. 染色的成功验证了反证法所证明色数的正确性, 从而解决了完全三部图K_3,5,p的点可区别一般全染色问题.     

K3,5,p的点可区别的一般全染色

首先, 利用色集合事先分配法, 反证探讨完全三部图K_3,5,p(p≥5)的点可区别一般全色数, 给出当p较小时的特殊性证明以及当p逐渐增大时的规律性证明； 其次, 利用构造染色法对完全三部图K_3,5,p进行染色, 给出染色方案. 染色的成功验证了反证法所证明色数的正确性, 从而解决了完全三部图K_3,5,p的点可区别一般全染色问题.     

轮、扇以及完全二部图K1,n和K2,n的点可区别VE-全染色

设G是阶至少为2的简单图.在点可区别正常全染色的基础上,提出了图G的点可区别一般全染色,即VE-全染色,并且得到了轮、扇和完全二部图K1,n和K2,n的点可区别VE-全色数,据此提出了一个猜想.     

完全二部图K_(6,n)(6≤n≤38)的点可区别E-全染色

考虑完全二部图K_(6,n)(6≤n≤38)的点可区别E-全染色.利用组合分析法、反证法及构造染色的方法,给出一类特殊完全二部图的点可区别E-全染色.结果表明:当6≤n≤10时,K_(6,n)的点可区别E-全色数为5;当11≤n≤38时,K_(6,n)的点可区别E-全色数为6.     

完全二部图K_(6,8)的点强可区别全染色

利用组合分析法,考虑完全二部图K_(6,8)的点强可区别全染色方案,给出一种可行的染色方案.结果表明,完全二部图K_(6,8)的点强可区别全色数为10.     

圈的无重复分数染色

考虑使得图G存在无重复的k-重n-染色的所有数对(n,k),其比值n/k的下确界定义为图G的无重复分数染色数.圈图的无重复分数染色数在文献中已有研究,除了C10,C14和C17之外的所有圈图的无重复分数染色数都已被确定,讨论并给出了这3个圈图的无重复分数染色数的上下界.     

超图的分数着色和分数团

超图是最一般最复杂的离散结构,是图的自然推广,但是图中的一些定义和结论并不是都能轻而易举地推广到超图中.给出超图分数着色和分数团的定义,这与特殊情形下的图的分数着色和分数团的定义是相容的,并将图的分数着色和分数团的一些结论在超图中进行了推广.     

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

设G是一个简单图,f是一个从V(G)∪ E(G)到{1,2,…,k}的映射.对每个v∈V(G),令Cf(v)={f(v)}∪{f(vw)|w∈V(G),vw∈E(G)}.如果f是G的正常全染色且u,v∈V(G),一旦uv∈E(G),就有Cf(u)≠Cf(v),那么称f为G的邻点可区别全染色(简称为k-AVDTC).设xat(G)=min{k|G存在k-AVDTC},则称xat(G)为G的邻点可区别全色数.给出了路、圈、完全图、完全二分图、星、扇和轮的Mycielski图的邻点可区别全色数.     

关于图K2n+1-E(2 K2)的邻点可区别全色数

用K2n 1-E(2K2)表示2n 1阶的完全图删掉两条不相邻的边所得到的图,给出了图K2n 1-E(2K2)的邻点可区别全色数.     

Cm×Kn的邻点可区别全染色

设G（V，E）是阶数至少为2的简单连通图，k是正整数，V∪E到{1，2，3，…，k）的映射f满足：对任意uυ，υw∈E（G），u≠w，有f（uv）≠f（υw）；对任意uυ∈E（G），有，（u）≠，（υ），f（u）≠f（uυ），f（υ）≠f（uυ）；那么称f为G的k-正常全染色，若，还满足对任意uυ∈E（G），有C（u）≠C（υ），其中C（u）={（u））∪{f（uυ）｜uυ∈E（G），υ∈V（G）），那么称，为G的k-邻点可区别的全染色（简记为k-AVDTC），称min{k｜G有k-邻点可区别的全染色）为G的邻点可区别的全色数，记作xat（G）．本文得到了圈Cm和完全图Kn的笛卡尔积图Cm×Kn邻点可区别的全色数．     

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

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

图K（r，2m）的邻点可区别全染色

在等完全r-部图全染色的研究中,首先确定了每部有2个点的完全r-部图的全色数;然后利用已得到的结果进一步研究每部有n个点的完全r-部图的全色数．采用上述思路研究了等完全卜部图的邻点可区别全染色,利用图分解的方法给出了每部有2个点的完全r-部图的邻点可区别全色数;并给出了每部有偶数个点的等完全r-部图的邻点可区别全色数．     

两类广义图r-冠图的分数色数

图的着色问题是图论的重要研究课题之一,分数色数作为正常色数的一个推广在计算机的许多领域中有着重要的应用.此处给出了广义圈、广义轮图的r-冠图的分数色数的计算公式.