Datensatz

Zusammenfassung

We show an $O(1.344^n) = O(2^{0.427n})$ 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. We apply 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.