Feature Request: Implement Graph Colouring Algorithm

[THIRU-1074]

Detailed description

I would like to request the implementation of a Graph Colouring Algorithm as a feature in this repository. Graph colouring is a way of assigning labels (often referred to as "colours") to the vertices of a graph such that no two adjacent vertices share the same label.

Context

This algorithm has multiple applications, including:

• Scheduling Problems: Assigning timeslots to tasks without conflicts.
• Map Coloring: Ensuring that no two adjacent regions share the same color.
• Register Allocation in Compilers: Minimizing the use of registers in code generation.

Possible implementation

Implementation of a Greedy Graph colouring Algorithm as a baseline. This algorithm assigns the smallest possible colour to each vertex while ensuring that no two adjacent vertices share the same colour. Additionally, an implementation of Backtracking can be provided to find more optimal solutions for graphs that require a minimal number of colours.

Additional information

(https://en.wikipedia.org/wiki/Graph_coloring)

[ritk20]

Implementation of graph colouring using backtracking exists here. I guess other colouring algorithms can be added.

[THIRU-1074]

Yes , DSatur is good to be implemented, this algorithm has better performance compared to existing one in repo.

[github-actions[bot]]

This issue has been automatically marked as abandoned because it has not had recent activity. It will be closed if no further activity occurs. Thank you for your contributions.