COLOR02/03/04: Graph Coloring and its Generalizations

Announcements

COLOR02/03/04 is a series of activities to effort to encourage research on computational methods for graph coloring problems, to evaluate alternative approaches using a common testbed, and to stimulate discussion on present and future directions in computational combinatorial optimization.

The Series consists of two workshops and one volume of refereed papers.

Mailing List

Join the mailing list for ongoing information.

Computational Symposium (CP2002)

A Computational Symposium was held in conjuction with Constraint Programming 2002.

Math Programming Symposium

A series of 3-4 sessions will be held at International Symposium on Mathematical Programming, Copenhagen, Denmark, August 18-22.

Deadline for submissions: April 1.

Paper selection: April 25.

Paper submission process:

All extended abstracts should be submitted through our online submission form. Abstracts should be 5-10 pages in length.

Note: If at all possible, please be sure to attempt to solve all of the instances listed in the COLOR02 computational results.

Refereed Volume

A refereed volume on this topic will be published by Discrete Applied Mathematics. Submissions for this volume are solicited from those who presented at CP2002 and those who present at ISMP2003, as well as relevant papers not presented at either.

Papers with a computational component must provide solution values/computation time for the instances marked (*) below (for graph coloring) or for all the instances given (for the generalizations). Papers must also provide the times for the Benchmark Program given below in order to allow cross-paper comparisons.

Full paper submission deadline: March 15, 2004

While no particular paper format is required for submission, there are latex style files from Elsevier that may be used.

Paper submission process: Email paper to trick@cmu.edu or send four copies to

Michael Trick
GSIA Room 341B
Carnegie Mellon University
Pittsburgh, PA 15213
USA

Topic

The Series is be on the topic "Graph Coloring and its Generalizations". This topic was chosen due to the wide applicability of graph coloring and the variety of solution approaches that have been proposed. This series builds off of a DIMACS Computational Challenge from the fall of 1993, where graph coloring was one of the problems addressed. In addition to the basic graph coloring problem, results are also solicited for the related problems of "multi-coloring" (assigning multiple colors to each node) and bandwidth allocation models (those with minimum difference requirements on the colors on adjacent nodes).

More formally, given a graph G=(V,E), node weights k(i) and edge weights d(i,j), we define four problems:

Possible topics suitable for the Series include:

All papers should have some computational aspect.

Organizers

The organizers of this Series are

Benchmarking Machines and Testing Solutions

Since the computations will be done on different machines, please download the benchmark tar file, compile the program dfmax and run the program on r500.b, reporting the resulting computation time.

Marco Chiarandini has developed a code to test solutions for validity (updated 2002/10/24).

Chirag Patel has provided a zip file with a modified benchmark file to work under Windows.

Allen van Gelder has provided a UNIX shell script to eliminate any duplicate edges in a file (some benchmark files include both edges (i,j) and (j,i)). Be sure to rename the file elim_dup.csh to match up with the instructions.

Instances

These graphs are in a modification of the DIMACS file format. Each line of the graph begins with a letter that defines the rest of the line. The legal lines are

Graph Coloring Instances

In addition to the following instances, Joe Culberson has generators for Equipartite IID, Flat, and Evacuation graphs which have a guaranteed upper bound on the chromatic number. See his notes for exploring phase transitions. Also, for larger problems, there are graphs from the clique part of the DIMACS Challenge.

Notes:

Coloring with Fixed Sets

In the following, some or all nodes must choose from the sets given by "f" lines.

Notes:

Bandwidth and multicoloring instances

The following can be used in bandwidth (edge weights) multicoloring (node weights) or both simply by ignoring unwanted information (edge weights for multicoloring and node weights for bandwidth). They can even be used for graph coloring by ignoring both!

Notes:

Further Information

The primary source of information for this Series is the web page:

http://mat.gsia.cmu.edu/COLORING03

Interested in the Series? Join the mailing list for ongoing information.

Bibliographies

koster.doc
Description: Annotated Bibliography on Frequency Assignment by Dr. Ir. Arie M. C. A. Koster (koster@zib.de) available at http://fap.zib.de
L(h,k) page
Description: Survey of L(h,k) labelling results by Dr. Tiziana Calamoneri (calamo@dsi.uniroma1.it).
marco.ps marco.pdf
Description: Graph coloring bibliography by Dr. Marco Chiarandini (machud@intellektik.informatik.tu-darmstadt.de).
Elsevier-web-of-science.doc
Description: Abstracts found on Elsevier and on Web of Science by a search for graph coloring and frequency assignment.
international-abstracts-in-or.doc
Description: Abstracts found in International Abstracts in O.R. by a search for graph coloring and frequency assignment.

Links

Some links that may help in this Series: