Graph Coloring Algorithms

[JohnnyWan1123]

Description

Implement algorithms to verify k-colorings, find valid colorings using greedy/DSatur algorithms, and compute chromatic number for small graphs.

Tasks

• Implement k-coloring verification
• Implement greedy coloring algorithm
• Implement DSatur algorithm for better coloring
• Add chromatic number computation (backtracking for small graphs)
• Detect coloring conflicts and report them
• Support both vertex and edge coloring
• Write unit tests for various graph types

Acceptance Criteria

• Coloring verification works correctly
• Greedy algorithm produces valid colorings
• DSatur produces better colorings than greedy
• Chromatic number computed for graphs up to 10 nodes
• Clear feedback on coloring conflicts
• Unit tests cover all coloring scenarios