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.
2. Cameron, P. J. (1994). Combinatorics: Topics, Techniques, Algorithms. Cambridge University Press. Retrieved from http://books.google.co.uk/books?id=xQqGQgAACAAJ
3. Biggs, N., Lloyd, E. K., & Wilson, R. J. (1986). Graph Theory, 1736-1936. New York, NY, USA: Clarendon Press.