This is the Graph Colouring exercise from Computer Science Distilled.
This gist contains a simple starting point for implementations in Ruby which deals with parsing the input file and a simple structure for Graph data. It does not implement the algorithm, which is left as an exercise for you.