Bentz, Cédric Costa, Marie-Christine de Werra, Dominique Picouleau, Christophe Ries, Bernard 2008 An extension of the basic image reconstruction problem in discrete tomography is considered: given a graph G = (V,E) and a family equation image of chains Pi together with vectors h(Pi) = (h1, . . . , hik), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = hij. 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 V1,...Vk 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. application/pdf https://folia.unifr.ch/global/documents/307833 https://folia.unifr.ch/documents/307833/files/paths-rero.pdf eng info:eu-repo/semantics/altIdentifier/doi/10.1002/net.20218 info:eu-repo/semantics/openAccess License undefined Networks. - 2008, vol. 51, no. 4, p. 256-267 Computer Networks and Communications Hardware and Architecture Software Information Systems info:eu-repo/classification/udc/004 On a graph coloring problem arising from discrete tomography http://purl.org/coar/resource_type/c_6501