Chromnum

The chromatic number of a graph G is the minimum set of colors by which nodes (or vertices) of a graph are colored exhaustively, such that no two adjacent nodes share the same color. Calculating the chromatic number of a graph is an NP (verifiable in nondeterministic polynomial time) - complete problem (Skiena 1990, pp. 211-212). Or, in the words of Harary (1994, p. 127), "No convenient method is known for determining the chromatic number of an arbitrary graph." Graph coloring has been studied as an algorithmic problem since the early 1970s: the chromatic number problem is one of Karp’s 21 NP-complete problems. One of the major applications of graph coloring, register allocation in compilers, was introduced in 1981.
This web-server presents a novel and simple Algorithm which calculates the chromatic number for undirected graphs.

Type a tag for your graph :

(optional)

Type (or copy-paste) your 1-0 adjacency matrix
in the following text-box :


The (NxN) matrix should be symmetric and
in the specified Format given in the text box
 Format-description:
 Matrix elements should either be 0 or 1 seperated by a single whitespace
 Diagonal elements may be 0 (ideally) or 1 : will be treated as 0
 Maximum size: 50x50 (i.e., 50 nodes in the graph)