Graph Coloring with Decision Diagrams

We introduce an iterative framework for solving graph coloring problems using decision diagrams. The decision diagram compactly represents all possible color classes, some of which may contain edge conflicts. In each iteration, we use a constrained minimum network flow model to compute a lower bound and identify conflicts. Infeasible color classes associated with these conflicts … Read more

An improved DSATUR-based Branch and Bound for the Vertex Coloring Problem

Given an undirected graph, the Vertex Coloring Problem (VCP) consists of assigning a color to each vertex of the graph in such a way that two adjacent vertices do not share the same color and the total number of colors is minimized. DSATUR based Branch and Bound (DSATUR) is an effective exact algorithm for the … Read more

Exact Solution of Graph Coloring Problems via Constraint Programming and Column Generation

We consider two approaches for solving the classical minimum vertex coloring problem�that is, the problem of coloring the vertices of a graph so that adjacent vertices have different colors and minimizing the number of used colors, namely, constraint programming and column generation. Constraint programming is able to solve very efficiently many of the benchmarks but … Read more

A simple branching scheme for Vertex Coloring Problems

We present a branching scheme for some Vertex Coloring Problems based on a new graph operator called extension. The extension operator is used to generalize the branching scheme proposed by Zykov for the basic problem to a broad class of coloring problems, such as the graph multicoloring, where each vertex requires a multiplicity of colors, … Read more

On forests, stable sets and polyhedras associated with clique partitions

Let $G=(V,E)$ be a simple graph on $n$ nodes. We show how to construct a partial subgraph $D$ of the line graph of $G$ satisfying the identity: $\overline \chi(G)+\alpha(D)=n$, where $\overline \chi(G)$ denotes the minimum number of cliques in a clique partition of $G$ and $\alpha(D)$ denotes the maximum size of a stable set of … Read more

Set covering and packing formulations of graph coloring: algorithms and first polyhedral results

We consider two (0,1)-linear programming formulations of the graph (vertex-)coloring problem, in which variables are associated to stable sets of the input graph. The first one is a set covering formulation, where the set of vertices has to be covered by a minimum number of stable sets. The second is a set packing formulation, in … Read more

Optimal Direct Determination of Sparse Jacobian Matrices

It is well known that a sparse Jacobian matrix can be determined with fewer function evaluations or automatic differentiation \emph{passes} than the number of independent variables of the underlying function. In this paper we show that by grouping together rows into blocks one can reduce this number further. We propose a graph coloring technique for … Read more

Frequency Planning and Ramifications of Coloring

This paper surveys frequency assignment problems coming up in planning wireless communication services. It particularly focuses on cellular mobile phone systems such as GSM, a technology that revolutionizes communication. Traditional vertex coloring provides a conceptual framework for the mathematical modeling of many frequency planning problems. This basic form, however, needs various extensions to cover technical … Read more