Extending the Theory of Colour Graphs

Constrain Satisfaction Problems provide a framework for a wide variety of problems across a number of scientific disciplines. For example, the problems of scheduling use of shared experimental equipment such as space telescopes, of interpreting geometric information as required by modern drawing tools, and of designing the layout of silicon chips can all be seen as Constraint Satisfaction Problems.In general, it is difficult to solve such problem so researchers concentrate on expanding their knowledge of case that are tractable. Recently for a particular class of these problems progress has been made by considering a particular structure --- the solution graph --- that is associated with these problems. Our aim is to continue this progress by looking at solution graphs for a class of problems for which they have not previously been studied. It is hoped that this will lead to improved algorithms that will help us efficiently solve new problems.