On a graph coloring problem arising from discrete tomography
Cédric Bentz, Martín Costa, D. de Werra, Christophe Picouleau, Bernard Ries · Networks · 2007
Abstract 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 Pi together with vectors h(Pi) = (h ,…,h ), one wants to find a partition V1,…,Vk of V such that for each Pi and each color j, |Vj ∩ Pi| = h . 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. © 2007 Wiley Periodicals, Inc. NETWORKS, 2008