# colouring problem

The *colouring problem* is to assign a *colour* to every vertex of a graph such that no two adjacent vertices^{} have the same colour. These colours, of course, are not necessarily colours in the optic sense.

Consider the following graph:

$$\text{xymatrix}A\text{ar}\mathrm{@}-[r]\mathrm{\&}B\text{ar}\mathrm{@}-[r]\text{ar}\mathrm{@}-[d]\mathrm{\&}C\text{ar}\mathrm{@}-[r]\text{ar}\mathrm{@}-[dl]\mathrm{\&}F\text{ar}\mathrm{@}-[dl]\mathrm{\&}D\text{ar}\mathrm{@}-[r]\mathrm{\&}E\mathrm{\&}$$ |

One potential colouring of this graph is:

$$\text{xymatrix}{A}\text{ar}\mathrm{@}-[r]\mathrm{\&}{B}\text{ar}\mathrm{@}-[r]\text{ar}\mathrm{@}-[d]\mathrm{\&}{C}\text{ar}\mathrm{@}-[r]\text{ar}\mathrm{@}-[dl]\mathrm{\&}{F}\text{ar}\mathrm{@}-[dl]\mathrm{\&}{D}\text{ar}\mathrm{@}-[r]\mathrm{\&}{E}\mathrm{\&}$$ |

$A$ and $C$ have the same colour; $B$ and $E$ have a second colour; and $D$ and $F$ have another.

Graph colouring problems have many applications in such situations as scheduling and matching problems.

Title | colouring problem |
---|---|

Canonical name | ColouringProblem |

Date of creation | 2013-03-22 12:17:00 |

Last modified on | 2013-03-22 12:17:00 |

Owner | vampyr (22) |

Last modified by | vampyr (22) |

Numerical id | 7 |

Author | vampyr (22) |

Entry type | Topic |

Classification | msc 05C15 |

Synonym | coloring problem |

Synonym | colour |

Synonym | color |

Synonym | graph colouring |

Synonym | graph coloring |