Contact: wagner@konig.elte.hu

                          PROPOSAL

                       GRAPH COLORING

                       by Janos Wagner
                       Computer Center
                  Semmelweis Medical University

	We would like to study backtrack-like graph coloring algorithms.
Our primary purpose is to color a given graph with a fixed number (k) of
colors. Although some of our algorithms may use some randomization, we
want them to always give the correct answer i.e. they should stop in a
finite number of steps and give either a good coloring of the graph whith
k colors if it is possible or give the answer "the graph cannot be colored
whith k colors" otherwise.

	After having such algorithms we can either determine the chromatic
number whith binary search or we can approximate it by similar technics. The
idea behind this approach is that probably the running time whith k far from
the chromatic number will be much less than the running time whith the chro-
matic number itself.

	We would like to study the following type of algorithm:
It colors the verticies one after the other. In a middle step there are
colored and non-colored verticies and for all of the latter ones we have
a list whith the possible colors for that vertex. In a phase the algorithm
chooses (somehow) a non-colored vertex, chooses (somehow) a color from its
list and colors it. Then some administrations follows, for the (somehow
defined) neighborhood of the recently colored vertex the algorithm updates
the lists of possibble colors. If it finds an empty list that means that
this partial coloring cannot be finished for the whole graph (whith this
k colors), so the algorithm should backtrack. It finds the latest vertex
whith an untried color on its list, change its color to this untried one
and so on. Naturally, when backtracking, the algorithm reconstructs the
modified lists.

	We can alter three parts of the algorithm:
i)   How to choose the next vertex for coloring.
ii)  How to choose the color of it from its list.
iii) For how big neighborhood it should update the list.
We expect that the possibilty i) is the most important, its altering will
have the biggest effect on the performance of the algorithm.

For i):   We can use the following strategies to choose the next vertex to
be colored:
	choose at random
	breadth first
	depth first
	choose the one whith largest degree (in the whole graph or just
		in the uncolored part of the graph)
	choose the vertex whith minimum number of possible colors
	choose the one which, if colored, has the largest effect on
		its neighborhood
or combinations of the above.

For ii):  We can choose the color at random or the one which has the
smallest effect on the neighborhood. (The idea behind this is that at this
point we did choose the vertex and either we will find a good color of
it which can be extended to a good coloring of the whole graph or we
must try all of the possible colors for this vertex.)

For iii): Some possibilities for the neighborhood are
	immediate neighbors,
	the previous ones plus the neighbors of those neighbors whose
	color became unique,
	more difficult ways to choose them.

We expect that number of backtracks can be decreased significantly but
the running time will decreased slightly because of the administritation.
These types of algorithms are expected to color approximately 60 point
graphs using exactly chromatic_number_of_the_graph colors.

Budapest, December 21, 1992

						Ja'nos Wa'gner