圈与路联图点可区别Ⅰ-全染色和点可区别Ⅵ-全染色

Vertex-distinguishingⅠ-total colorings and vertex-distinguishing Ⅵ-total colorings of join-graph of cycle and path

一个图G的Ⅰ-全染色是指若干种颜色对图G的全体顶点及边的一个分配使得任意两个相邻点及任意两条相邻边被分配到不同颜色.图G的Ⅵ-全染色是指若干种颜色对图G的全体顶点及边的一个分配使得任意两条相邻边被分配到不同颜色.对图G的一个Ⅰ(Ⅵ)-全染色及图G的任意一个顶点x,用C(x)表示顶点x的颜色及x的关联边的颜色构成的集合(非多重集).如果f是图G的使用k种颜色的一个Ⅰ(Ⅵ)-全染色,并且u,v∈V(G),u≠v,有C(u)≠C(v),则称f为图G的k-点可区别Ⅰ(Ⅵ)-全染色,或k-VDITC(VDVITC).图G的点可区别Ⅰ(Ⅵ)-全染色所需最少颜色数目,称为图G的点可区别Ⅰ(Ⅵ)-全色数.利用组合分析法及构造具体染色的方法,讨论了圈与路的联图C_m∨P_n的点可区别Ⅰ(Ⅵ)-全染色问题,确定了这类图的点可区别Ⅰ(Ⅵ)-全色数,同时说明了VDITC猜想和VDVITC猜想对于这类图是成立的.

I -total coloring of a graph G is an assignment of several colors to the vertices and edges of graph G such that any two adjacent vertices receive different colors and any two adjacent edges receive different colors. Ⅵ-total coloring of a graph G is an assignment of several colors to the vertices and edges of graph G such that any two adjacent edges receive different colors. For I （;）-total coloring of graph G and a vertex x of graph G, C（x） is used to denote the set （not multiset） composed of color of x and colors of the edges incident with x. Let f be I（Ⅵ）-total coloring of a graph G using k colors and C（u）=;C（v） for any two different vertices u and v of graph G, then f is called a k-vertex- distinguishing I （Ⅵ）-total coloring of graph G, or k-VDITC （VDVITC） of graph G for short. The minimum number of colors required in a VDITC （VDVITC） is the vertex-distinguishing I （Ⅵ）-total chromatic number. The problems of vertex-distinguishing I （Ⅵ）-total colorings of the join-graph Cm V Pn of cycle and path are discussed by the method of combinatorial analysis and constructing concrete coloring. Meanwhile, vertex-distinguishing I （Ⅵ）-total chromatic numbers of graph Cm V P. are determined. The results illustrate that the VDITC conjecture and VDVITC conjecture are valid for graph Cm V Pn.