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

DOI10.1016/j.dam.2010.09.011zbMath1226.05116OpenAlexW2017702547MaRDI QIDQ617894

Martin Matamala, Steéphan Thomassé, Flavio Guíñez

Publication date: 14 January 2011

Published in: Discrete Applied Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/j.dam.2010.09.011

zbMATH Keywords

complete bipartite graphdiscrete tomographydegree sequences

Mathematics Subject Classification ID

Applications of graph theory (05C90) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70) Coloring of graphs and hypergraphs (05C15)

Related Items (9)

New sufficient conditions on the degree sequences of uniform hypergraphs ⋮ Colour degree matrices of graphs with at most one cycle ⋮ Extremal Theorems for Degree Sequence Packing and the Two-Color Discrete Tomography Problem ⋮ Half-regular factorizations of the complete bipartite graph ⋮ Packing tree degree sequences ⋮ Constructing bounded degree graphs with prescribed degree and neighbor degree sequences ⋮ A formulation of the wide partition conjecture using the atom problem in discrete tomography ⋮ A note on packing of graphic \(n\)-tuples ⋮ On the Degree Sequence of 3-Uniform Hypergraph: A New Sufficient Condition

Cites Work

• Unnamed Item
• Studies on directed graphs. I, II
• A theorem on flows in networks
• A short proof of Kundu's k-factor theorem
• On joint realization of (0,1) matrices
• Matrices of zeros and ones with fixed row and column sum vectors
• The k-factor conjecture is true
• On the computational complexity of determining polyatomic structures by X-rays
• Discrete tomography. Foundations, algorithms, and applications
• Valencies of graphs with 1-factors
• A solvable case of image reconstruction in discrete tomography
• On factorable degree sequences
• Algorithms for constructing graphs and digraphs with given valences and factors
• Using graphs for some discrete tomography problems
• Combinatorial Properties of Matrices of Zeros and Ones
• Reconstructing 3-Colored Grids from Horizontal and Vertical Projections Is NP-hard
• On the use of graphs in discrete tomography
• Reconstructing polyatomic structures from discrete X-rays: NP-completeness proof for three atoms

This page was built for publication: Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem