BipartiteMatchingAndCover[g] takes a bipartite graph g and returns a matching with maximum weight along with the dual vertex cover. If the graph is not weighted, it is ...

BipartiteMatching[g] gives the list of edges associated with a maximum matching in bipartite graph g. If the graph is edge weighted, then the function returns a matching with ...

BipartiteQ[g] yields True if graph g is bipartite.

BrelazColoring[g] returns a vertex coloring in which vertices are greedily colored with the smallest available color in decreasing order of vertex degree.

ChromaticNumber[g] gives the chromatic number of the graph, which is the fewest number of colors necessary to color the graph.

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.

ChvatalGraph returns a smallest triangle-free, 4-regular, 4-chromatic graph.

CircularEmbedding[n] constructs a list of n points equally spaced on a circle. CircularEmbedding[g] embeds the vertices of g equally spaced on a circle.

CliqueQ[g, c] yields True if the list of vertices c defines a clique in graph g.

CoarserSetPartitionQ[a, b] yields True if set partition b is coarser than set partition a; that is, every block in a is contained in some block in b.