Faculté des sciences économiques et sociales

On a graph coloring problem arising from discrete tomography

Bentz, Cédric ; Costa, Marie-Christine ; de Werra, Dominique ; Picouleau, Christophe ; Ries, Bernard

In: Networks, 2008, vol. 51, no. 4, p. 256-267

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... More

Add to personal list
    Summary
    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.