In fact, Vizing's proof implies an O(nm) time algorithm with ⌬ ϩ 1 colors for the edge-coloring problem. However, Holyer has shown that deciding whether a graph requires ⌬ or ⌬ ϩ 1 colors is NP-complete [10]. For a multigraph G, Shannon showed that Ј(G) Յ 3⌬/2 [16].
A number of parallel algorithms exist for the edge-coloring problem. Lev et al. [14] presented parallel edge-coloring algorithms with ⌬ colors for bipartite multigraphs. When ⌬ ϭ 2 k , their algorithm requires O(log ⌬ log n) time and O(n⌬) processors. Otherwise, their algorithm requires O(log ⌬ log 2 n) time and O(n⌬) processors on the EREW PRAM. Gibbons et al. [5] and Gibbons and Rytter [6] suggested algorithms for some other special graphs such as trees, outerplanar graphs, and Halin graphs. For trees, their algorithm requires O(log n) time and O(n) processors; for outplanar graphs, their algorithm requires O(log 3 n) time and O(n 2 ) processors; for Halin graphs, their algorithm requires O(log 2 n) time and O(n) processors. All of their algorithms run in the CREW PRAM, and the number of colors used is at most ⌬. For planar graphs, Chrobak and Yung [3] presented an edge-coloring algorithm with max͕⌬, 19͖ colors. Their algorithm runs in O(log 2 n) time and uses O(n) processors on the EREW PRAM [3]. Later, Chrobak and Nishizeki [4] improved the algorithm in [3] by reducing the number of colors to max͕⌬, 8͖. Their algorithm requires O(log 3 n) time and O(n 2 ) processors [4]
. He [9] also discussed the edge-coloring problem with ⌬ colors for planar graphs, his algorithm has the same complexity as that of [3]. For general graphs, the pioneer work was done by Karloff and Shmoys [13]. They presented an edge-coloring algorithm with ⌬ ϩ 1 colors for simple graphs, which requires O(⌬ 6 log 4 n) time and O(n 2 ⌬) processors, assuming the fastest known algorithm for finding maximal independent sets [7] is used. They also gave a randomized edge-coloring algorithm with ⌬ ϩ 20⌬ 1/2ϩ colors, ( Յ 1/4), which runs in O(log O(1) n) expected time and uses O(n O(1) ) processors (independent of ). For multigraphs, Upfal once presented an O(log 3 ⌬n) time algorithm with 3⌬/2 colors by using O(⌬n) processors (appears in [13]). For the special class of multigraphs of ⌬ ϭ 3, Karloff and Shmoys [13] presented an algorithm which runs in O(log n) time and uses O(n) processors.
In this paper we study two problems. The first problem