1982/08/01 by Richard Cole, John E. Hopcroft · 4 citations
Computer Science · Engineering · Mathematics · #Advanced Graph Theory Research #graph theory and CDMA systems #Computational Geometry and Mesh Generation #Bipartite graph #Combinatorics #Edge coloring #Mathematics #Graph coloring #Complete bipartite graph #Complete coloring #List coloring #Enhanced Data Rates for GSM Evolution #Discrete mathematics #Fractional coloring #Graph #Graph power #Computer science #Line graph
paper · doi:10.1137/0211043
openalex publication_date 1982/08/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/06/11
An algorithm for finding a minimal edge coloring of a bipartite graph in time O(E log V) is presented. Polynomial time algorithms for this problem have previously been given by Gabow and Kariv the best time bounds being O(E log sq V) and O(V sq log V). The algorithm is based on using fast methods for finding maximal matchings in semiregular bipartite graphs; an algorithm for finding a maximal matching in a general bipartite graph was given by Hopcroft and Karp. Two algorithms for finding such a matching are given. Although the second one always has a faster running time, the first one is presented for the sake of clarity.