Edge Coloring Algorithms on Graphs PR #7397
105 views
Skip to first unread message
Susan Varghese Padath
Apr 15, 2024, 10:21:51 AMApr 15
to networkx-discuss
Hello all,
We have implemented an algorithm for finding the edge coloring in a graph. It uses a technique similar to Misra & Gries Edge coloring algorithm, using fan recoloring and Kempe chain flipping.
Our implementation follows the coding style and conventions consistent with other algorithms in the project. We have used a dictionary with edges as keys and colors as values to represent the coloring, in line with the conventions used for vertex coloring. Our implementation is based on the concepts explained in the lecture notes : Graph coloring: Heawood and Brookstheorems, edge coloring.
In PR 7138, we've already implemented two algorithms tailored for bipartite graphs. The significance of these algorithms lies in their efficiency for coloring bipartite graphs, which inherently require only Δ (chromatic index) colors to be properly colored. However, the current algorithm fails to guarantee this optimal coloring for bipartite graphs. For instance, even for simple bipartite graphs like K3-3, it still requires Δ + 1 colors for proper coloring. Therefore, the algorithms in PR 7138 are still relevant.
Our implementation follows the coding style and conventions consistent with other algorithms in the project. We have used a dictionary with edges as keys and colors as values to represent the coloring, in line with the conventions used for vertex coloring. Our implementation is based on the concepts explained in the lecture notes : Graph coloring: Heawood and Brookstheorems, edge coloring.
In PR 7138, we've already implemented two algorithms tailored for bipartite graphs. The significance of these algorithms lies in their efficiency for coloring bipartite graphs, which inherently require only Δ (chromatic index) colors to be properly colored. However, the current algorithm fails to guarantee this optimal coloring for bipartite graphs. For instance, even for simple bipartite graphs like K3-3, it still requires Δ + 1 colors for proper coloring. Therefore, the algorithms in PR 7138 are still relevant.
In accordance with the contributors' guide, we have followed all guidelines, including the writing of decorators, tests, and other necessary components.
We are working on contributing to NetworkX as our Btech project, and we are eager to receive feedback. We are committed to making any required changes and improvements.
Your feedback would be greatly appreciated.
Regards
We are working on contributing to NetworkX as our Btech project, and we are eager to receive feedback. We are committed to making any required changes and improvements.
Your feedback would be greatly appreciated.
Regards
Susan
Reply all
Reply to author
Forward
0 new messages