Colouring
Vertices in graphs can be given colours to identify or label them. Although they may actually be rendered in diagrams in different colours, working mathematicians generally pencil in numbers or letters (usually numbers) to represent the colours.
Given a graph G (V,E) a k-colouring of G is a map ϕ : V → {1, ..., k} with the property that (u, v) ∈ E ⇒ ϕ(u) ≠ ϕ(v) - in other words, every vertex is assigned a colour with the condition that adjacent vertices cannot be assigned the same colour.
The chromatic number χ(G) is the smallest k for which G has a k-colouring.
Given a graph and a colouring, the colour classes of the graph are the sets of vertices given the same colour.
Read more about this topic: Glossary Of Graph Theory
Famous quotes containing the word colouring:
“Every philosophy is tinged with the colouring of some secret imaginative background, which never emerges explicitly into its train of reasoning.”
—Alfred North Whitehead (1861–1947)
“The innocent brightness of a new-born Day
Is lovely yet;
The Clouds that gather round the setting sun
Do take a sober colouring from an eye
That hath kept watch o’er man’s mortality;”
—William Wordsworth (1770–1850)