Graph colouring
<application> A constraint-satisfaction problem often used as a test case in research, which also turns out to be equivalent to certain real-world problems (e.g. register allocation).
Given a connected graph and a fixed number of colours, the problem is to assign a colour to each node, subject to the constraint that any two connected nodes cannot be assigned the same colour.
This is an example of an NP-complete problem.
See also four colour map theorem.
| < Previous Terms | Terms Containing graph colouring | Next Terms > |
| Grapes Grapevine graph Graph Algorithm and Software Package graph coloring | constraint satisfaction graph coloring register allocation | Graphic ALGOL Graphical Kernel System Graphical User Interface Graphic Display Interface Graphic Language |
