Adjacent vertex-distinguishing edge and total chromatic numbers of hypercubes

作者：Chen Meirun^*; Guo Xiaofeng

来源：Information Processing Letters, 2009, 109(12): 599-602.

DOI：10.1016/j.ipl.2009.02.006

• Edge coloring
• Total coloring
• Adjacent vertex-distinguishing edge coloring
• Adjacent vertex-distinguishing total coloring
• Adjacent vertex-distinguishing edge chromatic number
• Adjacent vertex-distinguishing total chromatic number
• Hypercubes
• Interconnection networks

An adjacent vertex-distinguishing edge coloring of a simple graph G is a proper edge coloring of G such that incident edge sets of any two adjacent vertices are assigned different sets of colors. A total coloring of a graph G is a coloring of both the edges and the vertices. A total coloring is proper if no two adjacent or incident elements receive the same color. An adjacent vertex-distinguishing total coloring h of a simple graph G = (V, E) is a proper total coloring of G such that H(u) not equal 54 H(v) for any two adjacent vertices u and v, where H(u) = {h(wu) | wu is an element of E(G)} U {h(u)} and H(v) = {h(xv) | xv is an element of E(G)} U {h(v)}. The minimum number of colors required for an adjacent vertex-distinguishing edge coloring (resp. an adjacent vertex-distinguishing total coloring) of G is called the adjacent vertex-distinguishing edge chromatic number (resp. adjacent vertex-distinguishing total chromatic number) of G and denoted by X(av)'(G) (resp. X(at)(G)). In this paper, we consider the adjacent vertex-distinguishing edge chromatic number and adjacent vertex-distinguishing total chromatic number of the hypercube Q(n), prove that X(av)'(Q(n)) = Delta(Q(n)) 1 for n >= 3 and X(at)(Q(n)) = Delta(Q(n)) 2 for n >= 2.

• 出版日期2009-5-31
• 单位厦门大学