Bentz, CédricCosta, Marie-Christinede Werra, DominiquePicouleau, ChristopheRies, Bernard2006-08-312006-08-312006-08-31200810.1002/net.20218https://infoscience.epfl.ch/handle/20.500.14299/233946WOS:00025704880000212696An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph $G=(V,E)$ and a family $\mathcal{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}\cap 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.discrete tomographyvertex coloringedge coloringtreechainschedulingtext::journal::journal article::research article