Journal of Graph Algorithms and Applications
http://jgaa.info ISSN: 1526-1719
|
DOI: 10.7155/jgaa.00178 Degree-constrained edge partitioning in graphs arising from discrete tomography Cedric Bentz , Marie-Christine Costa , Christophe Picouleau , Bernard Ries , and Dominique de Werra Vol. 13, no. 2, pp. 99-118, 2009. Regular paper Abstract Starting from the basic problem of reconstructing a 2-dimensional image 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 specified vertices. A variation where the graph is oriented is also presented. In addition we explore similar problems for the case where the underlying graph is a complete graph (instead of a complete bipartite graph).
|
Accepted: November 2008. Reviewed: September 2008. Final: January 2009. Published: February 2009. Submitted: February 2007. Revised: October 2008. Communicated by Larse Arge |
| Journal of Graph Algorithms and Applications |