On the Enumeration of Bipartite Minimum Edge Colorings
Yasuko Matsui, Takeaki Uno · Birkhäuser Basel eBooks · 2006
For a bipartite graph G = (V,E), an edge coloring of G is a coloring of the edges of G such that any two adjacent edges are colored in different colors. In this paper, we consider the problem of enumerating all edge colorings with the fewest number of colors. We propose a simple polynomial delay algorithm whose amortized time complexity is O(|V|) per output, whereas the previous fastest algorithm took O(|E| log |V|) time per output. Although the delay of the algorithm is O(|E||V|), the delay of our algorithm can be reduced to O(|V|) by using a simple modification with a queue of polynomial size. We show an improvement to reduce the space complexity from O(|V||E|) to O(|E| + |V|). Furthermore, we obtain a lower bound \( (|E| - |\hat V| + 1)\max \{ 2^{\Delta - 3} ,2(|\hat V|/2 + 1)^{\Delta - 3} /(\Delta - 1)\} /\Delta \) of the number of edge colorings included in G, where Δ is the maximum degree and \( \hat V \) is the set of vertices of the maximum degree.