A note on graph proper total colorings with many distinguishing constraints
Graph coloring theory has a wide range of applications in many scientific fields. As an application, graph distinguishing colorings may be connected with the frequency assignment problem in wireless communication. The vertices (nodes) of graphs (networks) represent transmitters, the set C[u,f] C [ u , f ] of colors assigned to a vertex u and the edges (links) incident to u under a total coloring f  indicates the frequencies usable. One constrain C[u,f]?C[v,f] C [ u , f ] ? C [ v , f ] ensures the corresponding two stations u, v can operate on a wide range of frequencies without the danger of interfering with each other. We propose new total colorings having more constraints for researching deeply the frequency assignment problem. Under a proper total coloring f of a simple graph G , f(u) f ( u ) and f(uv) f ( u v ) are the color assigned to a vertex u and the color assigned to an edge uv , respectively. We use C(f,u) C ( f , u ) to denote the set of colors assigned to the edges incident to u , C?f,u? C ? f , u ? the union of f(u) f ( u ) and the set of colors assigned to the neighbors of u , so we have other two color sets C[f,u]=C(f,u)?{f(u)} C [ f , u ] = C ( f , u ) ? { f ( u ) } , and C2[f,u]=C(f,u)?C?f,u? C 2 [ f , u ] = C ( f , u ) ? C ? f , u ? . We say f an adjacent vertex distinguishing total coloring (AVDTC) of G  if one constraint C[f,u]?C[f,v] C [ f , u ] ? C [ f , v ] holds for each edge uv of G, and the minimum number of k colors required for which G  admits an AVDTC is denoted as ? a s ? ( G ) , which is related with a conjecture: ? a s ? ( G ) ? ? ( G ) + 3 , where ?(G) ? ( G ) is the maximum degree. We call f a 4-adjacent vertex distinguishing total coloring (4-AVDTC) of G  if four distinguishing constraints C(f,x)?C(f,y) C ( f , x ) ? C ( f , y ) , C?f,x??C?f,y? C ? f , x ? ? C ? f , y ? , C[f,x]?C[f,y] C [ f , x ] ? C [ f , y ] and C2[f,x]?C2[f,y] C 2 [ f , x ] ? C 2 [ f , y ] hold simultaneously true for every edge uv of G, and the least number of k colors required for which G admits a k -4-AVDTC is denoted by ? 4 a s ? ( G ) . We conjecture ? 4 a s ? ( G ) ? ? ( G ) + 4 if any edge uv of G holds that the set of neighbors of the vertex u differs from the set of neighbors of the vertex v.
total coloring vertex distinguishing coloring edge-coloring