On a graph coloring problem arising from discrete tomography
An 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.
WOS:000257048800002
2008
51
4
256
267
REVIEWED