welcome:
location: GraphColouring

# Graph Colouring

## Problem Description

A graph is a set of nodes and a symmetric, binary link relation on nodes. Given a set of N colours, a graph is colourable if each node can be assigned a colour in such a way that any two nodes that are linked together cannot have the same colour.

## Predicates

• Output: chosenColour/2

## Input format

A number of node facts which give the names of the nodes. Node names are consecutive, ascending integers starting from 1.

A number of colour facts which give the names of the colours. Colour names start with the sequence "red", "green", "blue".

## Output format

A set of choosenColour predicates, one for each node, specifying the node's colour.

## Example(s)

Given the following input:

```node(1). node(2). node(3).
colour(red). colour(green). colour(blue).```

Resulting in the output:

`chosenColour(1,red). chosenColour(2,green). chosenColour(3,blue).`

## Problem Peculiarities

Type: Search Competition: System Track Complexity: NP-complete