This directory contains the program and the data files that serve as supplements
to the paper `On The Three Coloring Problem' by Mohammad R. Salavatipour.


File "Conf.dat" contains the set of 74 reducible configurations stored in
the following format. The first line of the file contains the number of configurations 
(i.e. 74), followed by the information about the configurations, each
separated by an empty line. The non-boundary vertices of a configuration are those 
vertices whose degree in the graph is the same as their degree in the configuration.
The other vertices are boundary vertices. The information about i'th configuration is 
saved in the following format:

- The first line is: "Conf i"
- The second line contains two positive integers: n m , where n is the number of 
   vertices and m is number of edges.
- The next m lines contain the adjacency list of the graph, each edge in a separate line.
- The next n lines contain the coordinates of the vertices, each vertex in a separate line.
   These information can be used to draw the configuration, but are *not* needed in the program.
- The next line contains k, the number of groups of the constrained boundary vertices; each group
  contains those boundary vertices that should *not* all have the same color. 
- The next k lines, contain the lists of the vertices of the constrained boundary groups. The vertices
  of each group are in one line, separated by a singe space, and the lines end with "*".

File reduce.c is the program to check the reducibility of the configurations, written in C.

File conf.ps contains the plane drawings of all the 74 reducible configurations.

File 3color.ps is the paper itself.