AlternatingPaths[g, start, ME] returns the alternating paths in graph g with respect to the matching ME, starting at the vertices in the list start. The paths are returned in ...

ChromaticPolynomial[g, z] gives the chromatic polynomial P(z) of graph g, which counts the number of ways to color g with, at most, z colors.

CoxeterGraph gives a non-Hamiltonian graph with a high degree of symmetry such that there is a graph automorphism taking any path of length 3 to any other.

CycleIndex[pg, x] returns the polynomial in x[1], x[2], ..., x[index[pg]] that is the cycle index of the permutation group pg. Here index[pg] refers to the length of each ...

Distances[g, v] returns the distances in nondecreasing order from vertex v to all vertices in g, treating g as an unweighted graph.

EdgeChromaticNumber[g] gives the fewest number of colors necessary to color each edge of graph g, so that no two edges incident on the same vertex have the same color.

EdgeColoring[g] uses Brelaz's heuristic to find a good, but not necessarily minimal, edge coloring of graph g.

FranklinGraph returns a 12-vertex graph that represents a 6-chromatic map on the Klein bottle. It is the sole counterexample to Heawood's map-coloring conjecture.

GraphJoin[g_1, g_2, ...] constructs the join of graphs g_1, g_2, and so on. This is the graph obtained by adding all possible edges between different graphs to the graph ...

GraphPower[g, k] gives the k\[Null]^th power of graph g. This is the graph whose vertex set is identical to the vertex set of g and that contains an edge between vertices i ...