Home  Issues  About JGAA  Instructions for Authors 
DOI: 10.7155/jgaa.00171
An Efficient Algorithm for the Nearly Equitable Edge Coloring Problem
Xuzhen Xie,
Mutsunori Yagiura,
Takao Ono,
Tomio Hirata, and
Uri Zwick
Vol. 12, no. 4, pp. 383399, 2008. Regular paper.
Abstract An edge coloring of a multigraph is nearly equitable
if, 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 coloring
can be solved in O(m^{2}/k) time,
where m and k are the numbers of edges and given colors, respectively.
In this paper, we present a recursive algorithm that runs
in O(mn log(m/(kn) +1) ) time,
where n is the number of vertices.
This algorithm improves the bestknown worstcase time complexity.
When k=O(1), the time complexity of all known algorithms is O(m^{2}),
which implies that this time complexity remains to be the best
for more than twenty years since 1982 when Hilton and de Werra
gave a constructive proof for the existence of a nearly equitable edge coloring
for any multigraph.
Our result is the first that improves this time complexity
when m/n grows to infinity;
e.g., m = n ^{ϑ} for an arbitrary constant ϑ > 1.

Submitted: July 2008.
Reviewed: September 2008.
Revised: October 2008.
Accepted: October 2008.
Final: November 2008.
Published: December 2008.
Communicated by
Dorothea Wagner

Journal Supporters
