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 fo 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 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, `svn://svn.macaulay2.com/Macaulay2/trunk/M2/Macaulay2/packages/Nauty.m2`, release number 13224.

- Functions and commands
- addEdges -- creates a list of graphs obtained by adding one new edge to the given graph in all possible ways
- areIsomorphic -- determines whether two graphs are isomorphic
- buildGraphFilter -- creates the appropriate filter string for use with filterGraphs and countGraphs
- countGraphs -- counts the number of graphs in the list with given properties
- filterGraphs -- filters (i.e., selects) graphs in a list for given properties
- generateBipartiteGraphs -- generates the bipartite graphs with a given bipartition
- generateGraphs -- generates the graphs on a given number of vertices
- generateRandomGraphs -- generates random graphs on a given number of vertices
- generateRandomRegularGraphs -- generates random regular graphs on a given number of vertices
- graph6ToSparse6 -- converts a Graph6 string to a Sparse6 string
- graphComplement -- computes the complement of a graph
- graphToString -- converts a graph to a string in the Graph6 format
- isPlanar -- determines if a given graph is planar
- neighborhoodComplements -- complements the neighborhood for each vertex, individually
- newEdges -- replaces disjoint pairs of edges by disjoint pairs of two-chains
- onlyPlanar -- removes non-planar graphs from a list
- relabelBipartite -- relabels a bipartite graph so all vertices of a given class are contiguous
- relabelGraph -- applies a vertex invariant based refinement to a graph
- removeEdges -- creates a list of graphs obtained by removing one edge from the given graph in all possible ways
- removeIsomorphs -- removes all isomorphs from a list of graphs
- sparse6ToGraph6 -- converts a Sparse6 string to a Graph6 string
- stringToEdgeIdeal -- converts a Sparse6 or Graph6 String to an edge ideal in the given polynomial ring
- stringToGraph -- converts a Sparse6 or Graph6 String to a Graph in the given polynomial ring

- Symbols