Informace o publikaci

A theorem about the channel assignment problem

Autoři

KRÁĽ Daniel SKREKOVSKI R

Rok publikování 2003
Druh Článek v odborném periodiku
Časopis / Zdroj SIAM Journal on Discrete Mathematics
Citace
Doi http://dx.doi.org/10.1137/S0895480101399449
Klíčová slova graph coloring; list-coloring; channel assignment problem
Popis 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.

Používáte starou verzi internetového prohlížeče. Doporučujeme aktualizovat Váš prohlížeč na nejnovější verzi.

Další info