An Algorithm for Coloring the Nodes of a Graph

Abstract

We study the problem of coloring the nodes of a graph such that two nodes joined by an arc are assigned different colors. An algorithm is presented which requires $~n^{3}$ time, where the graph contains $n$ nodes. This algorithm yields near-minimal colorings. The algorithm is based on the "coalescence" and "free coalescence" of nodes to yield simpler graphs. Based on these same operations, we derive an exhaustive search which examines at most $2^{m}$ cases, where $m$ arcs appear in the complement of the graph to be colored. Key words and phrases: Graph coloring, graph node coloring, graph vertex coloring.