$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积的邻点可区别全色数.     

C_m·F_n和C_m·Cn的邻点可区别VE-全色数

根据冠图C_m·F_n和C_m·C_n的结构性质,用穷染,递推的方法,讨论了两类冠图C_m·F_n和C_m·C_n的邻点可区别VE-全染色,得到了相应的色数,当m≥3,n≥3时,x′_(at)~(ve)(C_m·F_n)=4,x′_(at)~(ve)(C_m·C_n)=(?),并给出了一种染色方案.     

图的邻点可区别Ⅵ-全色数和邻点可区别E-全色数

利用穷染、递推的方法讨论了路、圈、完全图、轮和扇的邻点可区别Ⅵ-全染色.并用概率方法研究了一般图的邻点可区别E-全染色,给出了图的邻点可区别E-全色数的一个上界.即δ≥7且△≥28,则有x_(at)~e(G)≤10△,其中δ是图G的最小度,△是图G的最大度.     

图C_5∨K_t的邻点可区别全色数

设f是图G的一个正常全染色.对任意x∈V(G),令C(x)表示与点x相关联的边的颜色以及点x的颜色所构成的集合.若对任意uv∈E(G),有C(u)≠C(v),则称.f是图G的一个邻点可区别全染色.对一个图G进行邻点可区别全染色所需的最少的颜色的数目称为G的邻点可区别全色数,记为Xat(G).用C_5∨K_t表示长为5的圈与t阶完全图的联图.讨论了C_5∨K_t的邻点可区别全色数.利用正多边形的对称性构造染色以及组合分析的方法,得到了当t是大于等于3的奇数以及t是偶数且2≤t≤22时,X_(at)(C_5 V K_t)=t+6,当t是偶数且t≥24时,X_(at)(C_5 V K_t)=t+7.     

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积的邻点可区别全色数．     

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

简单图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...     

某些中间图的邻点可区别E-全色数

设G（V,E）是简单连通图,T（G）为图G的所有顶点和边构成的集合,并设C是k-色集（k是正整数）,若T（G）到C的映射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的邻点可区别E-全染色（简记为k-AVDETC）,并称χ_（at）~e（G）=min{k｜图G有k-邻点可区别E-全染色}为G的邻点可区别E-全色数.图G的中间图M（G）就是在G的每一个边上插入一个新的顶点,再把G上相邻边上的新的顶点相联得到的.探讨了路、圈、扇、星及轮的中间图的邻点可区别E-全染色,并给出了这些中间图的邻点可区别E-全色数.     

三类平方图的点边邻点可区别全色数

根据平方图的结构性质,用穷染,递推的方法,讨论了路,圈,扇的平方图的点边邻点可区别全染色,得到了相应的色数,即并给出了一种染色方案.     

一些图的Double图的点可区别全色数

文献【2】定义点可区别全染色,对—个图其所用最少染色数称为它的点可区别全色数．本文得到了星、扇和轮的Double图的点可区别全色数．     

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

图G的一个正常全染色被称为邻点可区别全染色,如果G中任意两个相邻点的色集合不同．本文用概率方法得到了邻点可区别全色数的一个上界．     

乘积图的全色数

本文得到了有关乘积图的全色数的一些结果,并利用这些结果证明了Mesh图和Tours-图均满足全色数猜想．特别,几乎所有的Mesh-图都是第一类图．     

关于图的星色数的一点注记

A star coloring of an undirected graph G is a proper coloring of G such that no path of length 3 in G is bicolored.The star chromatic number of an undirected graph G,denoted by χs(G),is the smallest integer k for which G admits a star coloring with k colors.In this paper,we show that if G is a graph with maximum degree △,then χs(G) ≤ [7△3/2],which gets better bound than those of Fertin,Raspaud and Reed.     

AVDTC Numbers of Generalized Halin Graphs with Maximum Degree at Least 6

In a paper by Zhang and Chen et al.（see [11]）, a conjecture was made concerning the minimum number of colors Xat（G） required in a proper total-coloring of G so that any two adjacent vertices have different color sets, where the color set of a vertex v is the set composed of the color of v and the colors incident to v. We find the exact values of Xat（G） and thus verify the conjecture when G is a Generalized Halin graph with maximum degree at least 6, A generalized Halin graph is a 2-connected plane graph G such that removing all the edges of the boundary of the exterior face of G （the degrees of the vertices in the boundary of exterior face of G are all three） gives a tree.     

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

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

On adjacent-vertex-distinguishing total coloring of graphs

In this paper, we present a new concept of the adjacent-vertex-distinguishing total coloring of graphs (briefly, AVDTC of graphs) and, meanwhile, have obtained the adjacent-vertex-distinguishing total chromatic number of some graphs such as cycle, complete graph, complete bipartite graph, fan, wheel and tree.