chromaticNumber -- Computes the chromatic number of a graph

Synopsis

• Usage:
chi = chromaticNumber G
• Inputs:
• G, an instance of the type Graph,
• Outputs:
• chi, an integer, The chromatic number of G

Description

The chromatic number of G is chi(G) = min{k | there exists a k-coloring of G}. A k-coloring of G is a partition into k sets of vertices such that in each of these sets, none of the members form edges with each other.

 i1 : G = cycleGraph 5; i2 : chromaticNumber G o2 = 3