点可区别边色数的一个上界

设G是简单图,f是从V(G)∪E(G)到{1,2,…,k]的一个映射.对每个u∈V(G),令C(u)={f(uv)|v∈V(G),uv∈E(G)].如果f是k-正常边染色,且对任意u,v∈V(G),有C(u)≠C(v),那么称f为图G的点可区别边染色(简称为k-VDEC).数x's(G)=min{k|G有k-VDEC}称为图G的点可区别边色数.本文通过应用概率方法,证明了对任意最大度△≥2的图G,x's(G)≤16△.     

点可区别边色数和点可区别全色数的两个上界

应用概率方法中的第一矩量原理和Markov不等式,证明了对于最大度为Δ的n阶图G,当Δ≥2时,其点可区别的边色数χv′d(G)≤nΔ(n-1),当n≥3,Δ≥1时,其点可区别的全色数χvt(G)≤2 nΔ(n-1).     

联图的邻点可区别无圈边染色

根据图的邻点可区别无圈边染色的定义,利用构造的方法讨论联图Pm∨Wn、Pm∨Fn、Pm∨Pn、Pm∨Sn和Cm,n的邻点可区别无圈边染色,并给出它们的邻点可区别无圈边色数及其证明,且均满足图的邻点可区别无圈边染色猜想.     

图的邻点可区别无圈边染色

对无孤立边的简单图G,设G是一个正常边染色,如果G中任何两种颜色导出的子图是森林,即G中没有双色圈,且相邻点所关联的色集合不同,则称之为图G的邻点可区别无圈边染色。本文应用Lovász局部引理,即概率的方法确定了图G的一个邻点可区别无圈边染色的上界。     

图的点可区别星边色数的一个上界

图\,$G$\,的点可区别星边边色数, 记为\,$\chi'_{\rm vds}{(G)}$, 是图\,$G$\,的点可区别星边染色所用色的最小数目. 得到了一些特殊图的星边染色,
并证明了若图\,$G$\,是一个最小度不小于\,5, 且顶点数不超过\,$\Delta^7$\,的图时, $\chi'_{\rm vds}{(G)}\leqslant {14\Delta^{2}}$, 其中\,$\Delta$\,是图\,$G$\,的最大度.     

图的邻点可区别无圈边染色的渐近性质

对无孤立边的简单图G,和G的一个k-正常边染色法,使得G中任意的圈上的边至少出现三种不同颜色且G中任意两相邻的点所关联的边的色集合不同时,称为G的k-邻点可区别无圈边染色法;G中k-邻点可区别无圈边染色法中最小的k,称为邻点可区别无圈边色数.本文使用Lova′sz局部引理,得到了邻点可区别无圈边色数的一个上界.     

图的邻点可区别无圈边染色

提出了邻点可区别无圈边染色的概念及其相关猜想,并证明了对于一个没有孤立边的图G,如果它的邻点可区别边染色数X'as(G)=ε,那么存在一个常数r,如果围长g(G)≥r△log△,那么G的邻点可区别无圈边染色数至多为ε 1.     

图C_m∨W_n的点可区别边色数

对于图G的一个k-正常边染色,若满足不同点所关联边色集合不同,则称此染色法为点可区别边染色法.其所用最少颜色数称为该图的点可区别边色数.得到了图与轮的联图的点可区别边色数.     

若干图的Mycielski图的点可区别均匀边色数

简单图G的正常边染色f,若对于任意u,v∈V（G）,有C（u）≠C（v）,称,是图G的点可区别边染色,其中C（u）={f（uv）│uv∈E（G）}。若满足││Ei│—│Ej││≤1（i,j=1,2,…,k）,其中任意e∈Ei,f（e）=i（i=1,2,…,k）,称f是图G的点可区别均匀边染色。讨论了若干图的Mycielski图的点可区别均匀边染色。     

图Pm∨Wn的点可区别边色数

对网G的正常边染色，若满足不同点的点所关联边色集合不同，则称此染色法为点可区别的边染色法，其所用最少染色数称为该罔的点可区别边色数．得到了路与轮的联网的点可区别边色数。     

图的邻点可区别星边色数的一个上界

提出了图的邻点可区别星边染色及邻点可区别星边色数χ’ass(G)的概念,并用Lovász局部引理证明了若G=(V,E)是一个最小度为δ(G)≥3的简单无向图,则χ’ass(G)≤「32Δ32?。     

图的点可区别IE-全色数的一个上界

用概率方法研究图的点可区别IE-全色数的一个上界,得到:如果δ≥7且16Δ≤n≤Δ⁷/[32×10⁵(Δ+1)] +1, 则χ^ie_vt(G)≤16Δ ,这里n是G的阶,δ是G中点的最小度数,Δ是G中点的最大度数。       

图P_m V W_n的点可区别边色数

对图G的正常边染色,若满足不同点的点所关联边色集合不同,则称此染色法为点可区别的边染色法,其所用最少染色数称为该图的点可区别边色数．得到了路与轮的联图的点可区别边色数．     

若干积图的点可区别边染色

证明了:(1)两个n(n2)阶完全图的积图的点可区别边色数为2n. (2)对阶至少是3的完全图Kn,若χ′vd(G)=Δ(G),则χ′vd(G×Kn)=n+Δ(G).(3)若χ′vd(Gi)=Δ(Gi),i=1,2,则χ′vd(G1×G2)=Δ(G1)+Δ(G2).     

图的无圈边染色的一个结果

为了研究简单图G的无圈边染色,利用线性一时间算法思想证明了最大顶点度为4的简单图G。如果G中任意一条边的两个端点的度数之和不超过6,则其无圈边色数不超过5。     

Reexploring the upper bound for the chromatic number of graphs

The upper bound of the chromatic number of simple graphs is explored. Its original idea comes from Coffman, Hakimi and Schmeichel, who recently studied the chromatic number of graphs with strong conditions. In this paper, corresponding conditions are weakened and the result proves that of Ershov and Kozhukhin's.     

PmVPn的点可区别边色数

研究了Pm V Pn的点可区别边染色,并得到了PmVPn的点可区别边色数.     

六角系统关联色数与邻点可区别关联色数

通过运用嵌入法,得到了平面中任意六角系统以及六角系统的r-冠图的关联色数和邻点可区别关联色数。