# Glossary

### chromatic index

The chromatic index $\chi^{\prime}(G)$ of a graph $G$ is the minimal number of colours in a proper edge-colouring of $G$.

### chromatic number

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

### chromatic polynomial

The chromatic polynomial $\chi(G, k)$ of a graph $G$ is the number of $k$-colourings of $G$.

### degree

The degree of a vertex $v \in V(G)$ is the number of edges incident with $v$ in $G$.

### Euler path

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

### independent

An independent set of vertices in a graph $G$ is a set of vertices $A \subseteq V(G)$ such that the induced subgraph $G(A)$ is empty.

### induced subgraph

A subgraph $H$ of a graph $G$ is called an induced subgraph if there is a nonempty subset $S$ of $V(G)$ such that $H = G[S]$. (Chartrand & Zhang, 2008, p. 29)

### line graph

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

### path

A path (or walk (Cameron, 1994, p. 160)) is as a sequence of vertices and edges $v_{0},e_{1},v_{1},e_{2},v_{2},\ldots,v_{r-1},e_{r},v_{r}$ in which each edge $e_{i}$ joins vertices $v_{i-1}$ and $v_{i}$ $(1\leq i\leq r)$. (Biggs, Lloyd, & Wilson, 1986, p. 9)

### regular graph

A graph $G$ is regular if all vertices in $V(G)$ have the same degree in $G$.

## References

1. Chartrand, G., & Zhang, P. (2008). Chromatic Graph Theory (1st ed.). Chapman & Hall/CRC.