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₂ n, where m and n denote the number of edges and vertices respectively. For arbitrary graphs, a coloring with load at most frac(3, 4) m + O (sqrt(Δ m)) of Azuma's martingale inequality. This bound cannot be improved in general: almost all graphs have to be colored with load at least frac(3, 4) m - sqrt(3 m n).