Hiding Our Colors

A study looking for harder classes of graphs was presented at the CP95 Workshop on Studying and Solving Really Hard Problems held September 23, 1995 in Cassis, France. This paper, Hiding our colors co-authored with Adam Beacham and Denis Papp, presents first results from a generating program available here. (The paper is also available via ftp://ftp.cs.ualberta.ca/pub/joe/Preprints/ssrhpclr.ps.gz). This program generates graphs which have a hidden $k$-coloring. These graphs are generated with a variety of parameter variations that will be useful for testing different coloring algorithms. The purpose of this is twofold:

To allow comparisons of algorithms across graphs with varying characteristics.
To aid in the identification of instances of graph coloring problems that are hard to answer with any algorithm.

In this paper we describe several classes of $k$-colorable graphs which have various defining parameters. These are often motivated by questions of how to hide colorings that are significantly different than the colorings likely to be found by various heuristic algorithms.

For example, Br\'{e}laz's DSATUR algorithm\cite{bre79} tends to color denser regions of the graph first. It works quite well compared to other algorithms on geometric graphs\cite{jams91} which tend to have large cliques. In contrast, we define Girth Inhibited and Weight Biased graphs with the thought that DSATUR may be thwarted. We find some very intriguing results on the latter class reported in section 3.3.

joe@cs.ualberta.ca