

![0_image_0.png](0_image_0.png)

## 7.1 Graph Coloring

Graph coloring is an important and hard problem with applications in scheduling, assignment of radio frequencies, and computer optimization [17, 23, 26]. A
proper coloring assigns different colors to adjacent nodes. We want the chromatic polynomial for the chromatic number, i.e. the number of graph **colorings**
with minimal colors. Graph coloring is a useful benchmark, because it **gives us a** scalable problem, so that we can apply DDS to instances of varying complexity. The constraint model. For a given undirected graph g **and a number of colors**
c we introduce one variable per node with the initial domains 0..(c − **1). For**
each maximal clique of size > **2, we post an** All-different constraint on the corresponding variables. This maximizes the propagation necessary to **solve these**
problems but still enables DDS as we discuss below. For all remaining edges we add binary inequality constraints. The test sets**. We generated the two test sets GC-30 and GC-50 of graphs** with 30 and 50 nodes. For each size, random graphs were obtained by inserting an edge of the complete graph with a fixed uniform edge probability P
e**. This**
was done using the Erd˝os-R´enyi random graph generator GTgraph [12]. For each edge probability P
e**from 16 to 40 percent, 2000 graphs were generated and their**
colorings counted via DFS and DDS. To test highly degenerated problems (with many solutions) as well, we stopped after 1 million solutions. Results**. For the test sets, Tab. 1 compares the time consumption and search**
tree size by average ratios of DFS and DDS ( **DF S**
DDS **). A figure of 100 thus means**