# chromatic number

The *chromatic number ^{}* of a graph is the minimum number of colours required to colour it.

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{\&}$$ |

This graph has been coloured using $3$ colours. Furthermore, it’s clear that it cannot be coloured with fewer than $3$ colours, as well: it contains a subgraph^{} ($BCD$) that is isomorphic to the complete graph^{} of $3$ vertices. As a result, the chromatic number of this graph is indeed $3$.

This example was easy to solve by inspection. In general, however, finding the chromatic number of a large graph (and, similarly, an optimal colouring) is a very difficult (NP-hard) problem.

Title | chromatic number |
---|---|

Canonical name | ChromaticNumber |

Date of creation | 2013-05-16 21:23:44 |

Last modified on | 2013-05-16 21:23:44 |

Owner | mathcam (2727) |

Last modified by | unlord (1) |

Numerical id | 9 |

Author | mathcam (1) |

Entry type | Definition |

Classification | msc 05C15 |

Related topic | ChromaticNumberAndGirth |

Related topic | FourColorConjecture |

Related topic | ChromaticPolynomial |

Related topic | ChromaticNumberOfASpace |