若干图类的邻强边染色

研究了若干图类的邻强边染色 .利用在图中添加辅助点和边的方法 ,构造性的证明了对于完全图 Kn和路 Lm 的笛卡尔积图 Kn× Lm,有χ′as(Kn× Lm) =△ (Kn× Lm) +1 ,其中△ (Kn× Lm)和χ′as(Kn× Lm)分别表示图 Kn× Lm的最大度和邻强边色数 .同理验证了 n阶完全图 Kn的广义图 K(n,m)满足邻强边染色猜想 .     

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

设P_(n,k)是一个简单图,其顶点集和边集分别为:V(P_(n,k))={u_0,u_1,…u_(n-1),v_0,v_1,…v_(n-1)},E(P_(n,k))={u_iu_(i+1),u_iv_i,v_iv_(1+k)},则称P_(n,k)为广义Peterson图,其中n≥5,0相似文献   

路、圈的广义Mycielski图的邻点可区别Ⅰ-全色数

图G的邻点可区别Ⅰ-全染色是一个满足相邻顶点色集合不同的Ⅰ-全染色,其中任意一点的色集合包含该顶点及其关联边所染的颜色.所需颜色的最小数称为邻点可区别Ⅰ-全色数,记作χ_atⁱ(G).研究了路和圈的广义Mycielski图的邻点可区别Ⅰ-全色数:对于阶数n≥2的路P_n,当n=2,3,4时,有χ_atⁱ(M(P_n))=n+1;否则,χ_atⁱ(M(P_n))=n.对于阶数n≥3的圈C_n,当n=3,4时,有χ_atⁱ(M(C_n))=5;否则,χ_atⁱ(M(C_n))=n.     

图K(r,2)的邻强边色数

本文给出了每部有2个点的完全r-部图(r≥2)的邻强边色数.     

路与星联图的均匀邻强边色数

如果图G的一个正常边染色满足相邻点的色集不同,且任意两种颜色所染边数相差不超过1,则称为均匀邻强边染色,其所用最少染色数称为均匀邻强边色数.本文得到在m=1,2,3,n≥1和m=n≥4时的均匀邻强边色数.     

完全图的广义Mycielski图的邻强边染色

对|V(G)|≥3的连通图G,若κ-正常边染色法满足相邻点的色集合不相同,则称该染色法为κ-邻强边染色,其最小的κ称为图G的邻强边色数。张忠辅等学者猜想:对|V(G)|≥3的连通图G,G≠C_5其邻强边色数至多为△(G)+2,利用组合分析的方法给出了完全图的广义Mycielski图的邻强边色数,从而验证了图的邻强边染色猜想对于此类图成立。     

四类粘接图的niche数

粘接图G1(u)⊙G2(υ)是将图G1的顶点u与图G2的顶点υ重合而得到的一个图．本文证明Pm(u)⊙Kn(u是Pm的起点或终点，n≥2)，Km⊙Kn(m，n≥2)，Pm(u)⊙Cn(n≥3)和Km⊙Cn(m≥2，n≥3)这四类图都是niche图.     

关于图的一般邻点可区别边染色

给出了轮图W_n、扇图F_n、风车图K_2~t、图D_(m,4)、图D_(m,n)、齿轮图W_n的一般邻点可区别色指标.     

两类积图的邻点可区别全染色

本文.证明了,当n≥2时,Xat(K_n×K′_n)=2n;当p,q≥2时,Xat(C_(2p)×K_(2q))=2q 3,其中K_n×K′_n是两个不同标号完全图的积图,C_(2p)×K_(2q)是偶圈和偶阶完全图的积图.     

系列平行图的邻强边色数

本文研究了系列平行图的邻强边染色.从图的结构性质出发,利用双重归纳和换色的方法证明了对于△(G)=3,4的系列平行图满足邻强边染色猜想;对于△(G)≥5的系列平行图G, 有△(G)≤x'as(G)≤△(G) 1,且x'as(G)=△(G) 1当且仅当存在两个最大度点相邻,其中△(G)和x'as(G)分别表示图G的最大度和邻强边色数.     

折叠立方体图的邻点可区别全色数

简单图G的全染色是指对G的点和边都进行染色．称全染色为正常的如果没有相邻或关联元素染同一种颜色．简单图G=（VE）的正常全染色^称为它的邻点可区别全染色如果对任意两个相邻顶点u、v,有H（u）≠H（v）,其中H（u）={（u））U{^（uw）｜uw∈E（G））而H（v）={h（u）}U{h（vx）｜vx∈E（G））．G...     

扇的倍图的邻点可区别边色数

设G(V,E)是阶数至少是3的简单连通图,若f是图G的k-正常边染色,使得对任意的uv∈E(G),C(u)≠C(v),那么称f是图G的k-邻点可区别边染色(k-ASEC),其中C(u)={f(uw)│uw∈E(G)},而χa′s(G)=min{k│存在G的一个k-ASEC},称为G的邻点可区别边色数.本文给出扇的倍图D(Fm)的邻点可区别边色数.     

由轮图导出的某些平面图类的星色数

图的星色数是通常色数概念的推广.本文求出了几类由轮图导出的平面图的星色数.前两类是由3-或5-轮图经细分等构造出的,其星色数分别为2+2/(2n+1),2+3/(3n+1)和2+3/(3n-1).第三类平面图是由n-轮图经过Hajos构造得到的,其星色数为3+1/n.本类图的星色数结果推广了已有结论.     

关于联图K_(2,n)∨P_m的邻点可区别的全染色

一个全染色被称为邻点可区别的如果它满足对任意两个相邻点所关联的色集合不同.本文给出了联图K2,n∨Pm的邻点可区别的全色数并且证明了它满足邻点可区别的全染色猜想.     

The Adaptable Chromatic Number and the Chromatic Number

We prove that the adaptable chromatic number of a graph is at least asymptotic to the square root of the chromatic number. This is best possible.     

大围长图的广义无圈染色

图的顶点染色称为是r-无圈的,如果它是正常染色,使得每一个圈C上顶点的颜色数至少为min{|C|,r}.图G的r-无圈染色数是图G的r-无圈染色中所用的最少的颜色数.我们证明了对于任意的r≥4,最大度为△、围长至少为2(r-1)△的图G的r-无圈染色数至多为6(r-1)△.     

$P_m\times K_n$的邻点可区别全色数

设 $G$ 是简单图. 设$f$是一个从$V(G)\cup E(G)$ 到$\{1, 2,\cdots, k\}$的映射. 对每个$v\in V(G)$, 令 $C_f (v)=\{f(v)\}\cup \{f(vw)|w\in V(G), vw\in E(G)\}$. 如果 $f$是$k$-正常全染色, 且对任意$u, v\in V(G), uv\in E(G)$, 有$C_f(u)\ne C_f(v)$, 那么称 $f$ 为图$G$的邻点可区别全染色(简称为$k$-AVDTC).数 $\chi_{at}(G)=\min\{k|G$ 有$k$-AVDTC\}称为图$G$的邻点可区别全色数.本文给出路$P_m$和完全图$K_n$ 的Cartesion积的邻点可区别全色数.     

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

研究了一些Mycielski图的点可区别均匀全染色(VDETC),利用构造法给出了路、圈、星和扇的Mycielski图的点可区别均匀全色数,验证了它们满足点可区别均匀全染色猜想(VDETCC).     

图的邻点强可区别全色数的上界

本文利用概率方法得到了图的邻点强可区别全色数的上界.