No-hole 2-distant colorings for Cayley graphs on finitely generated abelian groups

作者：Chang Gerard J^*; Lu Changhong; Zhou Sanming

来源：Discrete Mathematics, 2007, 307(14): 1808-1817.

DOI：10.1016/j.disc.2006.09.030

• channel assignment
• T-coloring
• no-hole 2-distant coloring
• Cayley graph

A no-hole 2-distant coloring of a graph Gamma is an assignment c of nonnegative integers to the vertices of Gamma such that vertical bar c(v) - c(w)vertical bar >= 2 for any two adjacent vertices v and w, and the integers used are consecutive. Whenever such a coloring exists, define nsp(Gamma) to be the minimum difference (over all c) between the largest and smallest integers used. In this paper we study the no-hole 2-distant coloring problem for Cayley graphs over finitely generated abelian groups. We give sufficient conditions for the existence of no-hole 2-distant colorings of such graphs, and obtain upper bounds for the minimum span nsp(Gamma) by using a group-theoretic approach.

• 出版日期2007-6-28
• 单位华东师范大学