# Glossary

### chromatic index

The *chromatic index* of a graph is the minimal
number of colours in a proper edge-colouring of .

### chromatic number

The *chromatic number* of a graph is the minimal number of colours
in a proper colouring of .

### chromatic polynomial

The *chromatic polynomial* of a graph is the number of
-colourings of .

### degree

The *degree* of a vertex is the number of edges incident with
in .

### Euler path

An *Euler path* in a multigraph is a path of distinct edges
in whose length is equal to the size of .

### independent

An *independent set of vertices* in a graph is a set of vertices
such that the induced subgraph
is empty.

### induced subgraph

A subgraph of a graph is called an *induced subgraph* if there
is a nonempty subset of such that .
(Chartrand & Zhang, 2008, p. 29)

### line graph

The *line graph* of a nonempty graph is that graph whose vertex
set is and two vertices and of are adjacent if
and only if and are adjacent edges in .
(Chartrand & Zhang, 2008, p. 44)

### path

A *path* (or *walk* (Cameron, 1994, p. 160)) is as a
sequence of vertices and edges
in which each edge
joins vertices and .
(Biggs, Lloyd, & Wilson, 1986, p. 9)

### regular graph

A graph is *regular* if all vertices in have the same
degree in .

## References

- Chartrand, G., & Zhang, P. (2008).
*Chromatic Graph Theory* (1st ed.). Chapman & Hall/CRC.
- Cameron, P. J. (1994).
*Combinatorics: Topics, Techniques, Algorithms*. Cambridge University Press. Retrieved from http://books.google.co.uk/books?id=xQqGQgAACAAJ
- Biggs, N., Lloyd, E. K., & Wilson, R. J. (1986).
*Graph Theory, 1736-1936*. New York, NY, USA: Clarendon Press.