Coding with Graphs graph theory in code

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

  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.