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(uv) 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〉C2[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 χas″(G), which is related with a conjecture: χas″(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]C2[f,x]≠C2[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 χ4as″(G). We conjecture χ4as″(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.

A proper edge-coloring of a simple graph G is called a vertex distinguishing edge-coloring if for any two distinct vertices u and v of G, the set of the colors assigned to the edges incident to u differs from the set of the colors assigned to the edges incident to v. We extend such distinguishing edge colorings to proper total colorings with many distinguishing constraints and color several kinds of graphs totally with the least number of colors such that the graphs admit proper total colorings having at least four distinguishing constraints.