We show an O(1.344 ⁿ )=O(2^{0.427 n}) algorithm for edge-coloring an n-vertex graph using three colors. Our algorithm uses polynomial space. This improves over the previous, O(2 ^n/2) algorithm of Beigel and Eppstein [1]. We extend a very natural approach of generating inclusion-maximal matchings of the graph. The time complexity of our algorithm is estimated using the “measure and conquer” technique.