---
tag: 0NCPXH194Y
kind: concept
name: Graph colouring
msc: [05C15]
sources:
  - url: https://en.wikipedia.org/wiki/Graph_coloring
    locator: Definition and terminology
same_as:
  wikidata: Q504843
  wikipedia: Graph coloring
---

## Summary

A colouring of a graph assigns colours to the vertices so that adjacent vertices get different colours. Colourings model scheduling and other conflict problems. The node [[graph colouring|0874138YP6]] gives the precise definition.