Premium
On a graph coloring problem arising from discrete tomography
Author(s) -
Bentz C.,
Costa M.C.,
de Werra D.,
Picouleau C.,
Ries B.
Publication year - 2008
Publication title -
networks
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.977
H-Index - 64
eISSN - 1097-0037
pISSN - 0028-3045
DOI - 10.1002/net.20218
Subject(s) - combinatorics , vertex (graph theory) , mathematics , partition (number theory) , graph coloring , extension (predicate logic) , graph , discrete mathematics , computer science , programming language
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