This webpage contains the directed graphs used for testing acyclic coloring algorithms corresponding with the following paper:

Talla Nobibon, F., Hurkens, C., Leus, R. and Spieksma, F.C.R. (2012).  Coloring graphs using two colors while avoiding monochromatic cycles.  INFORMS Journal on Computing, 24, 485-499.   (pdf) (supplement) (DOI)

The random instances containing 50 vertices each can be found here: zip-file.

The real-life instances stemming from a micro-economics application are here.

The instances are saved as .txt files.

For each instance, the first line with three columns contains successively the number n of vertices, the number of arcs and the density of that graph, which is the number of arcs divided by the total number of possible arcs (n(n-1)).  We assume that the vertices are numbered from 1 to n. Next, there are as many lines as the number of arcs.  Each of these lines contains in the first column the number identifying the outgoing vertex, the next column represents an arrow and the last column contains the number of the incoming vertices.

To obtain the instance sets with higher values of n (100, 200, 500, 1000 and 5000), please contact us.