Publication details
A theorem about the channel assignment problem
| Authors | |
|---|---|
| Year of publication | 2003 |
| Type | Article in Periodical |
| Magazine / Source | SIAM Journal on Discrete Mathematics |
| Citation | |
| Doi | http://dx.doi.org/10.1137/S0895480101399449 |
| Keywords | graph coloring; list-coloring; channel assignment problem |
| Description | 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) is an element of L(v) for each vertex v and c(u) - c(v) greater than or equal to 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) greater than or equal to 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 greater than or equal to 2 has an L(2, 1)-labeling using integers 0,...,Delta(2) + Delta - 1. |