近完全图的点可区别Ⅰ-全染色及Ⅵ-全染色  

Vertex-distinguishingⅠ-total coloring andⅥ-total coloring of almost complete graphs

作　　者：张生桂 陈祥恩 ZHANG Sheng-gui;CHEN Xiang-en(College of Mathematics and Statistics,Northwest Normal University,Lanzhou 730070,Gansu,China)

机构地区：[1]西北师范大学数学与统计学院,甘肃兰州730070

出　　处：《山东大学学报（理学版）》2021年第5期23-25,共3页Journal of Shandong University(Natural Science)

基　　金：国家自然科学基金资助项目(11761064,61163037)。

摘　　要：图G的一个一般全染色是指使用若干颜色对图G的全部顶点及边的一个分配,如果任意两个相邻点和两条相邻边染以不同颜色,则称为图G的Ⅰ-全染色;如果任意两条相邻边染以不同的颜色,则称为图G的Ⅵ-全染色。图G的一个Ⅰ-全染色(或Ⅵ-全染色)f,若对?u,v∈V(G),u≠v,都有C(u)≠C(v),其中C(x)表示在f下点x的颜色以及与x关联的边的色所构成的集合,则f称为图G的点可区别的Ⅰ-全染色(或点可区别Ⅵ-全染色),简称为VDIT染色(或VDVIT染色)。令χ^(i)_(vt)(G)=min{k|G存在k-VDIT染色},称χ^(i)_(vt)(G)为图G的点可区别Ⅰ-全色数。令χ^(vi)_(vi)(G)=min{k|G存在k-VDVIT染色},称χ^(vi)_(vi)(G)为图G的点可区别Ⅵ-全色数。利用分析法和反证法,讨论并给出了近完全图的点可区别Ⅰ-全色数和Ⅵ-全色数。Let G be a simple graph.Suppose f is a general total coloring of graph G(i.e.,an assignment of several colors to all vertices and edges of G),if any two adjacent vertices and any two adjacent edges of graph G are assigned different colors,then f is called anⅠ-total coloring of a graph G;if any two adjacent edges of G are assigned different colors,then f is called aⅥ-total coloring of a graph G.For anⅠ-total coloring(orⅥ-totalcoloring)f of a graph G,if C(u)≠C(v)for any two distinct vertices u and v of V(G),where C(x)denotes the set of colors of vertex x and the edges incident with x under f,then f is called a vertex distinguishingⅠ-total coloring(or vertex distinguishingⅥ-total coloring)of G.Let χ^(i)_(vt)(G)=min{k|G has a k-VDIT coloring},then χ^(i)_(vt)(G)is called the VDIT chromatic number of G.Let χ^(vi)_(vi)(G)=min{k|G has a k-VDVIT coloring},then χ^(vi)_(vi)(G)is called the VDVIT chromatic number of G.The VDIT coloring(or VDVIT coloring)of almost complete graphs and the VDIT chromatic number(VDVIT chromatic number)of them has been obtained by using analytical method and proof by contradiction.

关 键 词：完全图 Ⅰ-全染色 点可区别Ⅰ-全染色 点可区别Ⅰ-全色数 

分 类 号：O157.5[理学—数学]