Coloring Graphs with Minimal Edge Load

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 + Δ log 2 n , where m and n denote the number of edges and vertices respectively. For arbitrary graphs, a coloring with load at most 3 4 m + 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 3 4 m − 3 m n .