The Channel Assignment Problem with Variable Weights
Daniel Král͏̌ · SIAM Journal on Discrete Mathematics · 2006
A λ‐graph G is a (finite or infinite) graph with k types of edges, $x_1$‐edges,…, $x_k$‐edges. A labeling c of the vertices of G by nonnegative reals is proper with respect to reals $x_1,\ldots,x_k$ if the labels of the end‐vertices of an $x_i$‐edge differ by at least $x_i$. The span of the labeling c is the supremum of the labels used by c. The λ‐function $\lambda_G(x_1,\ldots,x_k)$ is the infimum of the spans of all the proper labelings with respect to $x_1,\ldots,x_k$. We show that the λ‐function of any graph G is piecewise linear in $x_1,\ldots,x_k$ with finitely many linear parts (unless the λ‐function is infinite). Moreover, we show that for all integers k and χ, there exist constants $C_{k,\chi}$ and $D_{k,\chi}$ such that the λ‐function of every λ‐graph G with k types of edges and chromatic number at most χ is comprised of at most $C_{k,\chi}$ linear parts, and that the coefficients of $x_1,\ldots,x_k$ of the linear functions comprising $\lambda_G(x_1,\ldots,x_k)$ are integers between 0 and $D_{k,\chi}$. Among others, our results yield proofs of the piecewise linearity conjecture, coefficient bound conjecture, and delta bound conjecture of Griggs and Jin [SIAM J. Discrete Math., 20 (2006), pp. 302–327].