On the minimum load coloring problem (Q2466019)

Given a graph with \(n\) vertices, \(m\) edges and maximum vertex degree \(\Delta\), the \textit{load distribution} of a coloring \(\varphi:\;V\rightarrow\{\text{red, blue}\}\) is a pair \(d_\varphi=(r_\varphi,b_\varphi)\), where \(r_\varphi\) is the number of edges with at least one end-vertex colored red and \(b_\varphi\) is the number of edges with at least one end-vertex colored blue. The minimum load coloring problem asks for finding a coloring \(\varphi\) such that the (maximum) load, \(l_\varphi:=\frac1m\cdot\max\{r_\varphi,b_\varphi\}\), is minimized. Authors prove that general problem is NP-hard. Besides, they give a polynomial time algorithm for trees and show upper bound for an optimal load. For graphs with genus \(g>0\) they show that a coloring with load \(\text{OPT}(1+o(1))\) can be computed in \(O(n+g\log n)\)-time by an approximation algorithm, if the maximum degree satisfies \(\Delta=o(\frac{m^2}{ng})\) and an embedding is given. Finally, it is shown that coloring with load at most \(\frac34+O(\sqrt{\Delta/m})\) can be found by analyzing a random coloring with Chebychev's inequality.