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 ? : = 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)log2n 1 / 2 + ( ? / m ) log 2 n . For graphs with genus g>0 g > 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 + g log n ) -time, if the maximum degree satisfies ? = o ( m 2 n g ) and an embedding is given. In the general situation we show that a coloring with load at most 3 4 + 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 3 4 ? n / m . Finally, we state some conjectures on how our results generalize to k -colorings for k>2 k > 2 .
graph coloring graph partitioning