On the minimum load coloring problem

Given a graph G=(V,E)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φ)dφ=(rφ,bφ), where rφrφ is the number of edges with at least one end-vertex colored red and bφ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φ:=1m⋅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)log2n1/2+(Δ/m)log2n. For graphs with genus g>0g>0, we show that a coloring with load OPT(1+o(1))OPT(1+o(1)) can be computed in O(n+glogn)O(n+glogn)-time, if the maximum degree satisfies Δ=o(m2ng) and an embedding is given. In the general situation we show that a coloring with load at most 34+O(Δ/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)G(n,m) we prove that for almost all graphs, the optimal load is at least 34−n/m. Finally, we state some conjectures on how our results generalize to k  -colorings for k>2k>2.