The load of a coloring φ:V→{red,blue} for a given graph G=(V,E) is a pair Lφ=(rφ,bφ), where rφ is the number of edges with at least one red end-vertex and bφ is the number of edges with at least one blue end-vertex. Our aim is to find a coloring φ such that lφ:=max{rφ,bφ} is minimized. We show that this problem is NP-complete. For trees, we give a polynomial time algorithm computing an optimal solution. This has load at most m/2+Δlog2n, where m and n denote the number of edges and vertices respectively. For arbitrary graphs, a coloring with load at most 34m+O(Δm) of Azuma's martingale inequality. This bound cannot be improved in general: almost all graphs have to be colored with load at least 34m−3mn.