若干Mycielski图的邻点可区别E-全染色

设G(V,E)是简单连通图,k是正整数,若V∪到{1,2,3,…,k}的映射f满足对任意uv∈E(G),有f(U)≠f(v),f(u)≠f(uv)f(v)≠f(uv),且C(u)≠C(v),其中C(u):{f(u)}∪{f(uv)|uv∈E(G)}.那么称f为G的k-邻点可区别的E-全染色(简记为k-AVDETC),并称X_(at)~e(G)=min{k|G有k-邻点可区别的E-全染色}为G的邻点可区别的E-全色数.本文讨论了路、圈、扇、星、轮及完全图的Mycielski图的邻点可区别E-全染色,得到了该类图的邻点可区别的E-全色数.     

Pm×Kn的邻点可区别全色数

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

轮与路的多重联图的邻点可区别E-全染色

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)∪E(G)到{1,2,…,k}的映射.如果(V)u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.给出了轮与路间的多重联图的邻点可区别E-全色数,其中C(u)={f(u)}∪ {f(uv)|uv∈E(G)}.     

轮与星的多重联图的邻点可区别E-全染色

G(V,E)是一个简单图,k是一个正整数,f是一个V(G)UE(G)到{1,2,…,k}的映射.如果■u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.给出了轮与星的多重联图的邻点可区别E-全色数.     

若干联图的邻点可区别-点边全染色

设G(V,E)是简单图,k是正整数.从V(G)∪E(G)到{1,2,…,k}的映射f被称作G的邻点可区别-点边全染色,当且仅当:■uv∈E(G),f(u)≠f(uv),f(v)≠f(uv),■uv∈E(G),C(u)≠C(v),且称最小的数k为G的邻点可区别-点边全色数.其中C(u)={f(u)}∪{f(uv)|uv∈E(G)},研究了一些联图的邻点可区别-点边全染色法,得到了它们的色数.     

S_n+W_n的邻点强可区别全色数

设G(V,E)是阶数不小于3的简单连通图,k是自然数,f是从V(G)∪E(G)到1,2,…,k的映射,满足:对任意的uv∈E(G),f(u)≠f(v),f(u)≠f(uv)≠f(v);对任意的uv,uw∈E(G)(v≠w),f(uv)≠f(uw);对任意的uv∈E(G),C(u)≠C(v),其中C(u)={f(u)}∪{f(v)uv∈E(G)}∪{f(uv)uv∈E(G)},则称f是图G的一个邻点强可区别的全染色法,简记作k-AVSDTC,且称χast(G)=min{k G的所有k-AVSDTC}为G的邻点强可区别的全色数.得到了星与轮联图的邻点强可区别的全色数.     

图的点可区别Ⅳ-全染色

设G是简单图,图G的一个k-点可区别Ⅳ-全染色(简记为k-VDIVT染色)f是指一个从V(G)UE(G)到{1,2,…,k}的映射,满足:uv,uw∈E(G),v≠w,有f(uv)≠f(uw);u,v∈V(G),u≠v,有C(u)≠G(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.数min{k|G有一个k-VDIVT染色}称为图的点可区别Ⅳ-全色数,记为χ_(vt)^(iv)(G).本文给出了双星S_(2n),轮W_n和扇F_n的点可区别Ⅳ-全色数.     

P_n~k(k≡2(mod3))的邻点可区别的强全染色

对简单图 G(V,E) ,V(Gk) =V(G) ,E(Gk ) =E(G)∪ { uv|d(u,v) =k} ,称 Gk为 G的 k次方图 ,其中d (u,v)表示 u,v在 G中的距离 .设 f为用 k色时 G的正常全染色法 ,对 uv∈ E(G) ,满足 C(u)≠ C(v) ,其中C(u) ={ f(u) }∪ { f(v) |uv∈ E(G) }∪ { f(uv) |uv∈ E(G) } ,则称 f 为 G的 k邻点可区别的强全染色法 ,简记作 k- ASVDTC,且称 χast(G) =min{ k|k- ASVDTC of G}为 G的邻点可区别的强全色数 .本文得到了 k≡2 (mod3)时的 χast(Pkn) ,其中 Pn 为 n阶路 .     

完全图及完全二部图的点可区别Ⅳ-全染色

设G是简单图,图G的一个k-点可区别Ⅵ-全染色(简记为k-VDIVT染色),f是指一个从V(G)∪E(G)到{1,2,…,k}的映射,满足:()uv,uw∈E(G),v≠w,有,f(uv)≠f(uw);()u,V∈V(G),u≠v,有C(u)≠C(v),其中C(u)={f(u)}∪{f(uv)|uv∈E(G)}.数min{k|G有一个k-VDIVT染色}称为图G的点可区别Ⅵ-全色数,记为x_(vt)~(iv)(G).讨论了完全图K_n及完全二部图K_(m,n)的VDIVT色数.     

若干笛卡尔积图的邻点可区别E-全染色

图G(V,E)的k是一个正整数,f是V(G)∪E(G)到{1,2,…,k}的一个映射,如果u,v∈V(G),则f(u)≠f(v),f(u)≠f(uv),f(v)≠f(uv),C(u)≠C(v),称f是图G的邻点可区别E-全染色,称最小的数k为图G的邻点可区别E-全色数.得到了Pm×Pn,Pm×Cn,Cm×Cn的邻点可区别E-全色数,其中C(u)={f(u)}∪{f(uv)uv∈E(G)}.     

P_n~k的均匀全染色

设G(V,E)是一个简单图,f是G的一个k-正常全染色,若f满足||Vi∪Ei|-|Vj∪Ej||≤1(i≠j),其中Vi∪Ei={v|f(v)=i}∪{e|f(e)=i},则称f为G的k-均匀全染色,简记为k-ETC.并称eχT(G)=min{k|G存在k-均匀全染色}为G的均匀全染色数.本文将通过很好的全染色方法得到eχT(Pkn)=5(n≥2k+1),并证明了对Pkn,[5]中猜想是正确的.     

D(β)-vertex-distinguishing total coloring of graphs

A new concept of the D(β)-vertex-distinguishing total coloring of graphs, i.e., the proper total coloring such that any two vertices whose distance is not larger than β have different color sets, where the color set of a vertex is the set composed of all colors of the vertex and the edges incident to it, is proposed in this paper. The D(2)-vertex-distinguishing total colorings of some special graphs are discussed, meanwhile, a conjecture and an open problem are presented.     

图全染色的几个定理

图的全染色是染色理论的重要内容 ,全染色猜想 :设 G是一个简单图 ,则 XT( G)≤△ ( G) +2是一个至今未解决的问题 .本文证明了对于一些图类全染色猜想是正确的 .     

树的Mycielski图的邻点可区别全色染色

A k-proper total coloring of G is called adjacent distinguishing if for any two adjacent vertices have different color sets.According to the property of trees,the adjacent vertex distinguishing total chromatic number will be determined for the Mycielski graphs of trees using the method of induction.     

高度平面图的邻点可区别全染色

图G 的邻点可区别全染色是G 的一个正常全染色, 使得每一对相邻顶点有不同的颜色集合. G的邻点可区别全色数χ_a′′ (G) 是使得G 有一个k- 邻点可区别全染色的最小颜色数k. 本文证明了: 若G 是满足最大度Δ(G) ≥ 11 的平面图, 则χ_a′′ (G) ≤ Δ(G) + 3.     

Adjacent strong edge colorings and total colorings of regular graphs

It is conjectured that χas(G) = χt(G) for every k-regular graph G with no C5 component (k 2). This conjecture is shown to be true for many classes of graphs, including: graphs of type 1; 2-regular, 3-regular and (|V (G)| - 2)-regular graphs; bipartite graphs; balanced complete multipartite graphs; k-cubes; and joins of two matchings or cycles.     

关于一类二部图的均匀邻点可区别全染色

若图的邻点可区别全染色的各色所染元素数之差不超过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积的邻点可区别全色数.     

On the adjacent-vertex-strongly-distinguishing total coloring of graphs

For any vertex u∈V(G), let T_N(U)={u}∪{uv|uv∈E(G), v∈v(G)}∪{v∈v(G)|uv∈E(G)}and let f be a total k-coloring of G. The total-color neighbor of a vertex u of G is the color set C_f(u)={f(x)|x∈TN(U)}. For any two adjacent vertices x and y of V(G)such that C_f(x)≠C_f(y), we refer to f as a k-avsdt-coloring of G("avsdt"is the abbreviation of"adjacent-vertex-strongly- distinguishing total"). The avsdt-coloring number of G, denoted by X_(ast)(G), is the minimal number of colors required for a avsdt-coloring of G. In this paper, the avsdt-coloring numbers on some familiar graphs are studied, such as paths, cycles, complete graphs, complete bipartite graphs and so on. We proveΔ(G) 1≤X_(ast)(G)≤Δ(G) 2 for any tree or unique cycle graph G.