Skip to Main content Skip to Navigation
Journal articles

Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem

Abstract : We consider the problem of coloring a grid using p colors with the requirement that each row and each column has a specific total number of entries of each color. Ryser (1957) [20], and independently Gale (1957) [10], obtained a necessary and sufficient condition for the existence of such a coloring when two colors are considered. This characterization yields a linear-time algorithm for constructing the coloring when it exists. Later, Gardner et al. (2000) [11], and Chrobak and Dürr (2001) [5], showed that the problem is NP-hard when p ⩾ 7 and p ⩾ 4 , respectively. The case p = 3 was an open problem for several years and has been recently settled by Dürr et al. (2009) [9]: it is NP-hard too. This grid coloring problem is equivalent to finding disjoint realizations of two degree sequences d 1 , d 2 in a complete bipartite graph K X , Y . These kinds of questions are well studied when one of the degree sequences has span zero or one, where the span of a function is the difference between its maximum and its minimum values. In [4], Chen and Shastri (1989) showed a necessary and sufficient condition for the existence of a coloring when d 1 + d 2 restricted to X or Y has span at most one. In terms of discrete tomography this latter condition means that for two colors, the sum of the number of occurrences of these colors in each row is k or k + 1 , for some integer k . In the present paper we prove an analog to Chen and Shastri’s characterization when d 1 + d 2 restricted to X and to Y has span at most two. That is, there exist integers k 1 and k 2 such that the sum of the number of occurrences of two of the colors in each row is k 1 − 1 , k 1 or k 1 + 1 , and in each column is k 2 − 1 , k 2 or k 2 + 1 . Our characterization relies on a new natural condition called the total saturation condition which, when not satisfied, gives a non-existence certificate of such a coloring that can be checked in polynomial time.
Document type :
Journal articles
Complete list of metadata

https://hal-lirmm.ccsd.cnrs.fr/lirmm-00806767
Contributor : Alexandre Pinlou <>
Submitted on : Tuesday, April 2, 2013 - 12:10:09 PM
Last modification on : Saturday, September 11, 2021 - 3:18:10 AM

Links full text

Identifiers

Citation

Guinez Flavio, Martin Matamala, Stéphan Thomassé. Realizing disjoint degree sequences of span at most two: A tractable discrete tomography problem. Discrete Applied Mathematics, Elsevier, 2011, 159, pp.23-30. ⟨10.1016/j.dam.2010.09.011⟩. ⟨lirmm-00806767⟩

Share

Metrics

Record views

437