Cartesian积与邻点可区别着色之间的关系（英文）  

Relation between Cartesian product and adjacent vertex distinguishing coloring

作　　者：王国兴 WANG Guoxing(Gansu Business Development Research Center, Lanzhou University of Finance and Economics, Lanzhou 730020, China College of Information Engineering, Lanzhou University of Finance and Economics, Lanzhou 730020, China)

机构地区：[1]兰州财经大学甘肃商务发展研究中心,甘肃兰州730020 [2]兰州财经大学信息工程学院,甘肃兰州730020

出　　处：《浙江大学学报（理学版）》2017年第5期520-525,共6页Journal of Zhejiang University（Science Edition）

基　　金：Supported by the National Natural Science Foundation of China(61662066);Gansu Business Development Research Center Project of Lanzhou University of Finance and Economics(JYYY201506);Key Science and Research Project of Lanzhou University of Finance and Economics(LZ201302)

摘　　要：图G的一个正常k-边着色是指k种颜色1,2,…,k对图G各边的一个分配,使得任意2条相邻边染以不同的颜色.对于图G的一个正常边染色f和G中任何一个顶点x,Sf(x)或S(x)表示与顶点x关联的边在f下的颜色所构成的集合.若对于图G中任意2个相邻顶点u和v,有S(u)≠S(v),则称f为图G的邻点可区别正常边染色.对图G进行邻点可区别正常边染色所需的最少颜色数,称为G的邻点可区别正常边色数,记为χ′a(G).图G的一个正常k-全染色是指k种颜色对图G的顶点和边的一个分配,使得任意2个相邻的或相关联元素染以不同的颜色.对于图G的一个正常全染色g和G中任何一个顶点x,使用Cg(x)或C(x)来表示顶点x的颜色(在g下)以及与顶点x关联的边在g下的颜色所构成的集合.若对于G中任意2个相邻顶点u和v,有C(u)≠C(v),则称g为图G的邻点可区别全染色.图G的邻点可区别全染色所需的最少颜色数称为图G的邻点可区别正常全色数,记为χ″a(G).主要讨论了Cartesian积和2种邻点可区别染色之间的关系.A proper k-edge coloring of a graph Gis an assignment of kcolors 1,2,…,kto edges of Gsuch that any two adjacent edges receive the different colors.For a proper edge coloring fof Gand any vertex xof G,we use Sf（x）or S（x）to denote the set of the colors assigned to the edges incident with x.If for any two adjacent vertices uand vof G,we have S（u）≠S（v）,then fis called the adjacent vertex distinguishing proper edge coloring of G（or AVDPEC of Gin brief）.The minimum number of colors required in an AVDPEC of Gis called the adjacent vertex distinguishing proper edge chromatic number of G,denoted byχ′a（G）.A proper k-total coloring of a graph Gis an assignment of kcolors 1,2,…,kto vertices and edges of Gsuch that any two adjacent or incident elements receive the different colors.For a proper total coloring gof Gand any vertex xof G,we use Cg（x）or C（x）to denote the set of the colors assigned to the vertex xand edges incident with x.If for any two adjacent vertices uand vof G,we have C（u）≠C（v）,then gis called the adjacent vertex distinguishing total coloring of G（or AVDTC of Gin brief）.The minimum number of colors required in an AVDTC of Gis called the adjacent vertex distinguishing total chromatic number of G,denoted byχ″a（G）.In this paper,we discuss the relation between Cartesian product and two types of adjacent vertex distinguishing coloring.

关 键 词：Cartesian积 正常边染色 正常全染色 邻点可区别边染色 邻点可区别全染色 

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