A Low Complexity based Edge Color Matching Algorithm for Regular Bipartite Multigraph

An edge coloring of a graph G is a process of assigning colors to the adjacent edges so that the adjacent edges represents the different colors. In this paper, an algorithm is proposed to find the perfect color matching of the regular bipartite multigraph with low time complexity. For that, the proposed algorithm is divided into two procedures. In the first procedure, the possible circuits and bad edges are extracted from the regular bipartite graph. In the second procedure, the bad edges are rearranged to obtain the perfect color matching. The depth first search (DFS) algorithm is used in this paper for traversing the bipartite vertices to find the closed path, open path, incomplete components, and bad edges. By the proposed algorithm, the proper edge coloring of D – regular bipartite multi-graph can be obtained in O (D.V) time.

@article{Karim2017,
  title     = {A Low Complexity based Edge Color Matching Algorithm for Regular Bipartite Multigraph},
  journal   = {International Journal of Advanced Computer Science and Applications},
  volume    = {8},
  number    = {3},
  year      = {2017},
  publisher = {The Science and Information Organization},
  author    = {Rezaul Karim and Muhammad Mahbub Hasan Rony and Md. Rashedul Islam and Md. Khaliluzzaman},
  doi       = {10.14569/IJACSA.2017.080335},
  url       = {https://doi.org/10.14569/IJACSA.2017.080335}
}