Browse Prior Art Database
Quick Links

# Speed-Up Technique for Exact Graph-Coloring Algorithms

IP.com Disclosure Number: IPCOM000101009D
Original Publication Date: 1990-Jun-01
Included in the Prior Art Database: 2005-Mar-16
Document File: 2 page(s) / 54K

IBM

## Related People

Philips, TK: AUTHOR

## Abstract

Disclosed is a technique which allows large sparse graphs to be colored exactly. As graph coloring is an NP complete problem, this algorithm cannot be used on all graphs. In practice, however, graphs tend to be sparse, and the invention proves very useful. Before detailing the invention, we present a definition due to Chaitin.

This text was extracted from an ASCII text file.
This is the abbreviated version, containing approximately 61% of the total text.

Speed-Up Technique for Exact Graph-Coloring Algorithms

Disclosed is a technique which allows large sparse graphs
to be colored exactly.  As graph coloring is an NP complete problem,
this algorithm cannot be used on all graphs.  In practice, however,
graphs tend to be sparse, and the invention proves very useful.
Before detailing the invention, we present a definition due to
Chaitin.

Definition: Let l' be a lower bound on the chromatic number of
a graph G. A vertex v e G is said to be unconstrained with respect
to l' if its degree is strictly less than l'.  A vertex that is not
unconstrained is said to be constrained.

An unconstrained vertex may be removed from a graph without
changing its chromatic number, as its neighbors can be colored in at
most l' -1 colors, assuring that an available color can always be
found for it.  Note that a vertex that is initially constrained may
later become unconstrained due to the removal of other unconstrained
vertices adjacent to it.

The invention disclosed herein is an algorithm to find a large
number of unconstrained vertices, which may then be removed from the
graph, allowing a substantially smaller graph to be input to an exact
coloring algorithm.  It employs the observation that in the kinds of
graphs that are encountered in practice, the majority of the
vertices are unconstrained with respect to the size of the largest
clique.  Even though finding the size of the largest clique is an
...