Fact: Calculating the chromatic number of a graph is an NP-complete
problem. Other such problems are the Hamiltonian circuit and traveling
salesman problems. These problems appear to be very hard to solve quickly
for an optimal solution.
Known Chromatic Numbers:
- The Chromatic Number of a complete graph with n vertices is n. A
complete graph is a graph in which each pair of vertices is connected by
an edge.
- The Chromatic Number of a cycle graph with n vertices is 3, if n is
odd, and 2 if n is even. A cycle graph is a graph with n vertices
containing a single circuit through all vertices.
- The Chromatic Number of a star graph with n vertices is 2. A
star graph is a tree with n+1 vertices with one vertex having valence n
and the others having valence 1.
- The Chromatic Number of a wheel graph with n vertices is 3, if n is
odd, and 4 if n is even. A wheel graph is a graph with n vertices formed
by
connecting a single vertex to all vertices of an n-1 vertex cycle graph.