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).
展开▼
机译：从重建二维图像的基本问题开始，该二维图像是由其在两个轴上的投影给出的，将一个边缘着色模型关联到一个完整的二分图中。 k = 3种颜色的情况的复杂性是开放的。考虑k = 3种颜色的变体和特殊情况，其中对应于某些颜色类别（例如颜色1和2）的并集的图形具有给定的结构（树，顶点不相交链，2因子等）。 ）。我们还研究特殊情况，这些情况对应于搜索2条不相交的链或经过指定顶点的循环。还介绍了图形的方向变化。此外，对于基础图是完整图（而不是完整的二部图）的情况，我们探索了类似的问题。
展开▼
