The chromatic number c(G) of a graph G is the minimum number of colors such that a coloring is possible.
Computing the chromatic number is NP-hard and thus coloring a graph is in general NP-hard as well.
| Given a graph
G = (N, E) a k-coloring of the graph is an assignment
N ® {1 , ..., k} such that
adjacent nodes are assigned different colors. The chromatic number c(G) of a graph G is the minimum number of colors such that a coloring is possible. Computing the chromatic number is NP-hard and thus coloring a graph is in general NP-hard as well. |
|
