Edge disjoint caterpillar realizations
István Miklós, Geneva Schlafly, Yuheng Wang, Zhangyang Wei · Discrete Applied Mathematics · 2020
Edge disjoint realization problems have connections for example to discrete tomography. In this paper, we consider the edge disjoint caterpillar realizations of tree degree sequences. We give necessary and sufficient conditions when two tree degree sequences have edge disjoint caterpillar realizations. We conjecture that an arbitrary number of tree degree sequences have edge disjoint realizations if every vertex is a leaf in at most one tree. We prove that the conjecture is true if the number of tree degree sequences is at most four. We also prove that the conjecture is true if n≥max{22k−11,396}, where n is the number of vertices and k is the number of tree degree sequences.