JavaScript is disabled for your browser. Some features of this site may not work without it.
An Algorithm for Coloring the Nodes of a Graph

Author
Wagner, Robert A.
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.
Date Issued
1970-10Publisher
Cornell University
Subject
computer science; technical report
Previously Published As
http://techreports.library.cornell.edu:8081/Dienst/UI/1.0/Display/cul.cs/TR70-79
Type
technical report