Cartesian积与邻点可区别着色之间的关系(Relation between Cartesian product and adjacent vertex distinguishing coloring) - WANGGuoxing(王国兴) (Zhejiang Daxue xuebao. Lixue ban, 2017)
A proper k-edge coloring of a graph G is an assignment of k colors 1, 2, …, k to edges of G such that any two adjacent edges receive the different colors. For a proper edge coloring f of G and any vertex x of 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 u and v of G, we have S(u)≠S(v), then f is called the adjacent vertex distinguishing proper edge coloring of G (or AVDPEC of G in brief). The minimum number of colors required in an AVDPEC of G is called the adjacent vertex distinguishing proper edge chromatic number of G, denoted by . A proper k-total coloring of a graph G is an assignment of k colors 1, 2, …, k to vertices and edges of G such that any two adjacent or incident elements receive the different colors. For a proper total coloring g of G and any vertex x of G, we use Cg(x) or C(x) to denote the set of the colors assigned to the vertex x and edges incident with x. If for any two adjacent vertices u and v of G, we have C(u)≠C(v), then g is called the adjacent vertex distinguishing total coloring of G (or AVDTC of G in brief). The minimum number of colors required in an AVDTC of G is called the adjacent vertex distinguishing total chromatic number of G, denoted by . In this paper, we discuss the relation between Cartesian product and two types of adjacent vertex distinguishing coloring.