On the minimum load coloring problem

Given a graph G = (V, E) with n vertices, m edges and maximum vertex degree Δ, 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_φ : = frac(1, m) ṡ max {r_φ, b_φ}, is minimized. This problems arises in Wavelength Division Multiplexing (WDM), the technology currently in use for building optical communication networks. 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 1 / 2 + (Δ / m) log₂ 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 log n)-time, if the maximum degree satisfies Δ = o (frac(m², n g)) and an embedding is given. In the general situation we show that a coloring with load at most frac(3, 4) + O (sqrt(Δ / m)) can be found by analyzing a random coloring with Chebychev's inequality. This bound describes the "typical" situation: in the random graph model G (n, m) we prove that for almost all graphs, the optimal load is at least frac(3, 4) - sqrt(n / m). Finally, we state some conjectures on how our results generalize to k-colorings for k > 2.