On the bipartite graph packing problem

DOI10.1016/J.DAM.2017.04.019MaRDI QIDQ2357142zbMATH OpenOpenAlexFDO

Authors Bálint Vásárhelyi

Publication date 19 June 2017

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

Full work available at URL https://arxiv.org/abs/1604.00934, http://publicatio.bibl.u-szeged.hu/16649/1/3236340-preprint.pdf

zbMATH Keywords

bipartitedegree sequencegraph packing

Mathematics Subject Classification ID

Vertex degrees (05C07) Edge subsets with special properties (factorization, matching, partitioning, covering and packing, etc.) (05C70)

Abstract: The graph packing problem is a well-known area in graph theory. We consider a bipartite version and give almost tight conditions on the packability of two bipartite sequences.

Cites work

• A theorem on flows in networks
• An \(\Omega{} (n^{4/3})\) lower bound on the randomized complexity of graph properties
• Combinatorial Properties of Matrices of Zeros and Ones
• Edge disjoint placement of graphs
• Extremal graph packing problems: Ore-type versus Dirac-type
• Extremal theorems for degree sequence packing and the two-color discrete tomography problem
• Graph Factors and Matching Extensions
• scientific article; zbMATH DE number 5174567 (Why is no real title available?)
• On packing bipartite graphs
• Packing bipartite graphs
• Packing two bipartite graphs into a complete bipartite graph
• Probability Inequalities for Sums of Bounded Random Variables
• Spanning trees in dense graphs
• Subgraphs of graphs. I
• The probabilistic method. With an appendix on the life and work of Paul Erdős.
• Weighted sums of certain dependent random variables

Cited in

(3)

• Bin-packing and matchings in threshold graphs
• Embedding graphs having Ore-degree at most five
• The b‐bibranching problem: TDI system, packing, and discrete convexity

This page was built for publication: On the bipartite graph packing problem

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2357142)