On a graph coloring problem arising from discrete tomography

An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = ( V , E ) and a family $\cal {P}$ of chains P i together with vectors h ( P i ) = ( h   i 1 ,…, h   i k ), one wants to find a partition V 1 ,…, V k of V such that for each P i and each color j , | V j ∩ P i | = h   i j . An interpretation in terms of scheduling is presented. We consider special cases of graphs and identify polynomially solvable cases; general complexity results are established in this case and also in the case where V 1 ,…, V k is required to be a proper vertex k ‐coloring of G . Finally, we examine also the case of (proper) edge k ‐colorings and determine its complexity status. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008