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] 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] 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) and f(uv) are the color assigned to a vertex u and the color assigned to an edge uv  , respectively. We use C(f,u) to denote the set of colors assigned to the edges incident to u  , C〈f,u〉 the union of 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)}, and 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] holds for each edge uv of G, and the minimum number of k colors required for which G   admits an AVDTC is denoted as View the MathML source, which is related with a conjecture: View the MathML source, where Δ(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] and 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 View the MathML source. We conjecture View the MathML source 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.

© 2004-2018 中国地质图书馆版权所有 京ICP备05064691号 京公网安备11010802017129号

地址:北京市海淀区学院路29号 邮编:100083

电话:办公室:(+86 10)66554848;文献借阅、咨询服务、科技查新:66554700