An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem - Xie, Xuzhen; Yagiura, Mutsunori; Ono, Takao; Hirata, Tomio; Zwick, Uri (Journal of Graph Algorithms and Applications, 2008)
An edge coloring of a multigraph is nearly equitableif, among the edges incident to each vertex,the numbers of edges colored with any two colors differ by at most two.It has been proved that the problem of finding a nearly equitable edge coloringcan be solved in O(m2/k) time,where m and k are the numbers of edges and given colors, respectively.In this paper, we present a recursive algorithm that runsin O(mn log(m/(kn) +1) ) time,where n is the number of vertices.This algorithm improves the best-known worst-case time complexity.When k=O(1), the time complexity of all known algorithms is O(m2),which implies that this time complexity remains to be the bestfor more than twenty years since 1982 when Hilton and de Werragave a constructive proof for the existence of a nearly equitable edge coloringfor any multigraph.Our result is the first that improves this time complexitywhen m/n grows to infinity;e.g., m = n ϑ for an arbitrary constant ϑ > 1. <!---->