Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

# 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