This project explores an algebraic approach to solving the NP-complete graph coloring problem. By leveraging computational algebraic geometry, the project aims to efficiently determine the k-colorability of graphs, with a particular focus on chordal graphs.
- Polynomial Systems: Implements polynomial equations to represent graph colorability, providing an algebraic perspective on the problem.
- Gröbner Basis Algorithm: Develops a custom algorithm to compute Gröbner bases for chordal graphs, offering a polynomial-time solution for specific graph classes.
- Real-World Applications: Demonstrates the utility of the approach in practical scenarios, such as scheduling and resource allocation.
- Timetable Scheduling: Applies graph coloring techniques to avoid scheduling conflicts.
- Resource Allocation: Optimizes resource distribution in systems by ensuring non-overlapping allocations.
- Sudoku Solver: Uses graph coloring to solve puzzles like Sudoku by ensuring valid number placements.
To get started with this project, clone the repository and open the Jupyter notebook to explore the implementation details.
git clone https://github.com/himanshutg/Graph_Coloring.git
jupyter notebook graph_coloring.ipynb