### A NP-complete problem

Co-authorsC. Bentz, M.C. Costa, C. Picouleau and B. Ries

The basic image reconstruction problem in discrete tomography consists in assigning some color for every pixel of a rectangular array in such a way that requirements on the number of occurrences of each color in the rows and columns are satisfied.

This can be modelled as a vertex coloring problem in a graph with additional constraints.

In a similar way, chromatic scheduling considers applications of coloring models to various types of scheduling problems; here also additional requirements have to be introduced in order to capture the essential constraints of the scheduling problem.

Here we shall be concerned with graph coloring models where, in
addition to the usual requirements occurring in coloring problems, we
will have a collection P of chains P_{i} of the associated graph and it will
be required that in each P_{i} color
j occurs exactly
h_{i}^{j} times, where the
h_{i}^{j} are given
integers.

We will examine special cases of graphs like trees, cacti and bipartite graphs. Polynomially solvable cases will be identified and general complexity results will be given. We will also relax some assumptions on colorings and study cases where the colorings need not be proper. The case of edge coloring (often used in basic timetabling models) will also be investigated. Open questions will finally be raised in relation with applications.

Keywordschromatic scheduling, discrete tomography, image reconstruction, graph coloring, complexity