# [BCP09] Degree-constrained edge partitioning in graphs arising from discrete tomography

**Revue Internationale avec comité de lecture : **
*Journal J. of Graph Algorithms and Applications*,

vol. 13(2),

pp. 99-118,
2009

**motcle: **

**Résumé: **
Starting from the basic problem of reconstructing a 2-dimensional im-
age given by its projections on two axes, one associates a model of edge
coloring in a complete bipartite graph. The complexity of the case with
k = 3 colors is open. Variations and special cases are considered for the
case k = 3 colors where the graph corresponding to the union of some color
classes (for instance colors 1 and 2) has a given structure (tree, vertex-
disjoint chains, 2-factor, etc.). We also study special cases corresponding
to the search of 2 edge-disjoint chains or cycles going through specied
vertices. A variation where the graph is oriented is also presented.
In addition we explore similar problems for the case where the under-
lying graph is a complete graph (instead of a complete bipartite graph).