Packing tree degree sequences

DOI10.1007/S00373-020-02153-0zbMATH Open1486.05040arXiv1704.03148OpenAlexW3010918251MaRDI QIDQ2175807FDOQ2175807

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

Publication date: 30 April 2020

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

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.

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

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

zbMATH Keywords

rainbow matchingdegree constrained edge partitioningtree 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)

Cites Work

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

Cited In (2)

• Edge disjoint caterpillar realizations
• Graphic sequences of trees and a problem of Frobenius

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)