A Theorem about the Channel Assignment Problem

Source abstract

A list channel assignment problem is a triple (G,L,w), where G is a graph, L is a function which assigns to each vertex of G a list of integers (colors), and w is a function which assigns to each edge of G a positive integer (its weight). A coloring c of the vertices of G is proper if c(v)\in L(v)$for each vertex v and$|c(u)-c(v)|\ge w(uv)$for each edge uv. A weighted degree$\deg_w(v)$of a vertex v is the sum of the weights of the edges incident with v. If G is connected,$|L(v)|>\deg_w(v)$for at least one v, and$|L(v)|\ge\deg_w(v)$for all v, then a proper coloring always exists. A list channel assignment problem is balanced if$|L(v)|=\deg_w(v)$for all v. We characterize all balanced list channel assignment problems (G,L,w) which admit a proper coloring. An application of this result is that each graph with maximum degree$\Delta\ge 2$has an L(2,1)-labeling using integers$0,\ldots,\Delta^2+\Delta-1$.