This package provides an interface from Macaulay2 to many of the functions provided in the software nauty by Brendan D. McKay, available at http://cs.anu.edu.au/~bdm/nauty/. The nauty package provides very efficient methods for determining whether given graphs are isomorphic, generating all graphs with particular properties, generating random graphs, and more.
Most methods can handle graphs in either the Macaulay2 Graph type as provided by the EdgeIdeals package or as Graph6 and Sparse6 strings as used by nauty. The purpose of this is that graphs stored as strings are greatly more efficient than graphs stored as instances of the class Graph. (See Comparison of Graph6 and Sparse6 formats.)
It is recommended to work with graphs represented as strings while using nauty-provided methods and then converting the graphs to instances of the class Graph for further work (e.g., computing the chromatic number).
The theoretical underpinnings of nauty are in the paper: B. D. McKay, "Practical graph isomorphism," Congr. Numer. 30 (1981), 45–87.
Version 1.4.1 of this package was accepted for publication in volume 3 of The Journal of Software for Algebra and Geometry: Macaulay2 on 2011-04-20, in the article Nauty in Macaulay2. That version can be obtained from the journal or from the Macaulay2 source code repository.
This documentation describes version 1.4.3.1 of Nauty.
The source code from which this documentation is derived is in the file Nauty.m2.