DIMACS Graph Format

**Last revision: May 08, 1993
Abbreviated: Bart Massey March 02, 2001**

An input file contains all the information about a graph needed to define a coloring problem.

In this format, nodes are numbered from 1 up to *n*
edges in the graph.

Files are assumed to be well-formed and internally consistent: node
identifier values are valid, nodes are defined uniquely,
exactly *m*
edges are defined, and so forth.

**Comments.**Comment lines give human-readable information about the file and are ignored by programs. Comment lines can appear anywhere in the file. Each comment line begins with a lower-case character**c**.c This is an example of a comment line.

**Problem line.**There is one problem line per input file. The problem line must appear before any node or arc descriptor lines. For network instances, the problem line has the following format.p FORMAT NODES EDGES

The lower-case character`p`signifies that this is the problem line. The`FORMAT`field is for consistency with the previous Challenge, and should contain the word ``edge''. The`NODES`field contains an integer value specifying*n*, the number of nodes in the graph. The`EDGES`field contains an integer value specifying*m*, the number of edges in the graph.**Edge Descriptors.**There is one edge descriptor line for each edge the graph, each with the following format. Each edge*(v,w)*appears exactly once in the input file and is not repeated as*(w,v)*.e W V

The lower-case character`e`signifies that this is an edge descriptor line. For an edge*(w,v)*the fields`W`and`V`specify its endpoints.

**Solution Line**s TYPE SOLUTION

The lower-case character`s`signifies that this is a solution line. The`TYPE`field denotes the type of solution contained in the file. This should be the string ``col'' denoting a graph coloring.The

`SOLUTION`field contains an integer corresponding to the solution value. This is the number of colors used for graph coloring.**Bound Line**b BOUND

The lower-case character

`b`signifies that this is a bound on the the solution. The`BOUND`field contains an integer value that gives a bound on the solution value. This bound is a lower bound on the number of colors needed for coloring the graph.**Label Line**l V N

The lower-case character

`l`signifies that this is a label line, used for graph coloring. The`V`field gives the node number for the node in the clique while the`N`field gives the corresponding label. There will be one label line for each node in the graph.

Exemples :

c FILE: myciel3.col

c SOURCE: Michael Trick (trick@cmu.edu)

c DESCRIPTION: Graph based on Mycielski transformation.

c Triangle free (clique number 2) but increasing

c coloring number

p edge 11 20

e 1 2

e 1 4

e 1 7

e 1 9

e 2 3

e 2 6

e 2 8

e 3 5

e 3 7

e 3 10

e 4 5

e 4 6

e 4 10

e 5 8

e 5 9

e 6 11

e 7 11

e 8 11

e 9 11

e 10 11

DIMACS Project: Rutgers University

Bart Massey