Graph colouring by maximal evidence edge adding

Graph colouring is one of the most studied NP-hard problems. Many problems of practical interest can be modelled as colouring problems. The basic colouring problem is to group items in as few groups as possible, subject to the constraint that no incompatible items end up in the same group. Classical examples of applications include timetabling and scheduling [25]. We describe an iterative heuristic algorithm for adding new edges to a graph in order to make the search for a colouring easier. The heuristic is used to decide which edges should be added by sampling a number of approximate colourings and adding edges which have fewest conflicts with the generated colourings. We perform some analysis of the number of approximate colourings that might be needed to give good bounds on the probability of including an edge which increases the chromatic number of the graph. Experimental results on a …