On the minimum load coloring problem extended abtract

Given a graph G = (V, E) with n vertices, m edges and maximum vertex degree A, the load distribution of a coloring φ: V → {red, blue} is a pair d_φ, = (r_φ, b_φ), where r _φ is the number of edges with at least one end-vertex colored red and b_φ is the number of edges with at least one end-vertex colored blue. Our aim is to find a coloring φ such that the (maximum) load, l_φ:= maxj{r_φ, b_φ}, is minimized. The problem has applications in broadcast WDM communication networks (Ageev et al., 2004). After proving that the general problem is NP-hard we give a polynomial time algorithm for optimal colorings of trees and show that the optimal load is at most m/2 + Δ log 2 n. For graphs with genus g > 0, we show that a coloring with load OPT(1 + o(1)) can be computed in O(n + g)-time, if the maximum degree satisfies Δ = 0(m₂/n _g) and an embedding is given. In the general situation we show that a coloring with load at most 3/4m + O(√Δm) can be found in deterministic polynomial time using a derandomized version of Azuma's martingale inequality. This bound describes the "typical" situation: in the random multi-graph model we prove that for almost all graphs, the optimal load is at least 3/4m - mn. Finally, we generalize our results to k-colorings for k > 2.