Packing tree degree sequences

DOI10.1007/S00373-020-02153-0MaRDI QIDQ2175807zbMATH OpenOpenAlexFDO

Authors Aravind Gollakota, Will Hardt, István Miklós

Publication date 30 April 2020

Published in Graphs and Combinatorics (Search for Journal in Brave)

Copyright license Creative Commons Attribution 4.0 International

Full work available at URL https://arxiv.org/abs/1704.03148

zbMATH Keywords

degree constrained edge partitioningrainbow matchingtree sequence packing keyword

Mathematics Subject Classification ID

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

Abstract: We consider packing tree degree sequences in this paper. We set up a conjecture that any arbitrary number of tree degree sequences without common leaves have edge disjoint tree realizations. This conjecture is known to be true for $2$ and $3$ tree degree sequences. In this paper, we give a proof for $4$ tree degree sequences and a computer aided proof for $5$ tree degree sequences. We also prove that for arbitrary $k$, $k$ tree degree sequences without common leaves and at least $2k-4$ vertices which are not leaves in any of the trees always have edge disjoint tree realizations. The main ingredient in all of the presented proofs is to find rainbow matchings in certain configurations.

Recommendations

• Degree sequence realizations with given packing and covering of spanning trees
• Packing almost stars into the complete graph
• Degree sequences and graphs with disjoint spanning trees
• On the tree packing conjecture
• Navigating between packings of graphic sequences

Cites work

• A note on a theorem of Erdős and Gallai
• A short proof of Kundu's k-factor theorem
• A simple criterion on degree sequences of graphs
• Colour degree matrices of graphs with at most one cycle
• Contributions to the theory of graphic sequences
• Degree-constrained edge partitioning in graphs arising from discrete tomography
• Disjoint Representation of Three Tree Realizable Sequences. I
• Disjoint Representation of Tree Realizable Sequences
• scientific article; zbMATH DE number 3169205 (Why is no real title available?)
• Packing of graphic n-tuples
• Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem
• The k-factor conjecture is true
• The wonderful Walecki construction

Cited in

(5)

• Navigating between packings of graphic sequences
• Edge disjoint caterpillar realizations
• Degree sequence realizations with given packing and covering of spanning trees
• Graphic sequences of trees and a problem of Frobenius
• Dense, irregular, yet always-graphic 3-uniform hypergraph degree sequences

This page was built for publication: Packing tree degree sequences

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