{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,28]],"date-time":"2025-09-28T12:45:37Z","timestamp":1759063537891,"version":"3.37.3"},"reference-count":14,"publisher":"Springer Science and Business Media LLC","issue":"3","license":[{"start":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T00:00:00Z","timestamp":1584662400000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"},{"start":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T00:00:00Z","timestamp":1584662400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/creativecommons.org\/licenses\/by\/4.0"}],"funder":[{"DOI":"10.13039\/501100011019","name":"NKFIH","doi-asserted-by":"crossref","award":["K116769","SNN-117879"],"award-info":[{"award-number":["K116769","SNN-117879"]}],"id":[{"id":"10.13039\/501100011019","id-type":"DOI","asserted-by":"crossref"}]}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":["Graphs and Combinatorics"],"published-print":{"date-parts":[[2020,5]]},"abstract":"<jats:title>Abstract<\/jats:title><jats:p>A degree sequence is a list of non-negative integers, <jats:inline-formula><jats:alternatives><jats:tex-math>$${D = d_1, d_2, \\ldots , d_n}$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>D<\/mml:mi><mml:mo>=<\/mml:mo><mml:msub><mml:mi>d<\/mml:mi><mml:mn>1<\/mml:mn><\/mml:msub><mml:mo>,<\/mml:mo><mml:msub><mml:mi>d<\/mml:mi><mml:mn>2<\/mml:mn><\/mml:msub><mml:mo>,<\/mml:mo><mml:mo>\u2026<\/mml:mo><mml:mo>,<\/mml:mo><mml:msub><mml:mi>d<\/mml:mi><mml:mi>n<\/mml:mi><\/mml:msub><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula>. It is called graphical if there exists a simple graph <jats:italic>G<\/jats:italic> such that the degree of the <jats:italic>i<\/jats:italic>th vertex is <jats:inline-formula><jats:alternatives><jats:tex-math>$$d_i$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:msub><mml:mi>d<\/mml:mi><mml:mi>i<\/mml:mi><\/mml:msub><\/mml:math><\/jats:alternatives><\/jats:inline-formula>; <jats:italic>G<\/jats:italic> is then said to be a realization of <jats:italic>D<\/jats:italic>. A tree degree sequence is one that is realized by a tree. In this paper we consider the problem of packing tree degree sequences: given <jats:italic>k<\/jats:italic> tree degree sequences, do they have simultaneous (i.e. on the same vertices) edge-disjoint realizations? We conjecture that this is true for any arbitrary number of tree degree sequences whenever they share no common leaves (degree-1 vertices). This conjecture is inspired by work of Kundu (SIAM J Appl Math 28:290\u2013302, 1975) that showed it 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 make progress towards proving our conjecture for arbitrary <jats:italic>k<\/jats:italic>. We prove that <jats:italic>k<\/jats:italic> tree degree sequences without common leaves and at least <jats:inline-formula><jats:alternatives><jats:tex-math>$$2k-4$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mn>2<\/mml:mn><mml:mi>k<\/mml:mi><mml:mo>-<\/mml:mo><mml:mn>4<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> vertices which are not leaves in any of the trees always have edge-disjoint tree realizations. Additionally, we show that to prove the conjecture, it suffices to prove it for <jats:inline-formula><jats:alternatives><jats:tex-math>$$n \\le 4k - 2$$<\/jats:tex-math><mml:math xmlns:mml=\"http:\/\/www.w3.org\/1998\/Math\/MathML\"><mml:mrow><mml:mi>n<\/mml:mi><mml:mo>\u2264<\/mml:mo><mml:mn>4<\/mml:mn><mml:mi>k<\/mml:mi><mml:mo>-<\/mml:mo><mml:mn>2<\/mml:mn><\/mml:mrow><\/mml:math><\/jats:alternatives><\/jats:inline-formula> vertices. The main ingredient in all of the presented proofs is to find rainbow matchings in certain configurations.<\/jats:p>","DOI":"10.1007\/s00373-020-02153-0","type":"journal-article","created":{"date-parts":[[2020,3,20]],"date-time":"2020-03-20T05:31:06Z","timestamp":1584682266000},"page":"779-801","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":2,"title":["Packing Tree Degree Sequences"],"prefix":"10.1007","volume":"36","author":[{"given":"Aravind","family":"Gollakota","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Will","family":"Hardt","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Istv\u00e1n","family":"Mikl\u00f3s","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2020,3,20]]},"reference":[{"key":"2153_CR1","first-page":"7","volume":"52","author":"B Alspach","year":"2008","unstructured":"Alspach, B.: The wonderful Walecki construction. Bull. Inst. Combin. Appl. 52, 7\u201320 (2008)","journal-title":"Bull. Inst. Combin. Appl."},{"issue":"2","key":"2153_CR2","doi-asserted-by":"publisher","first-page":"99","DOI":"10.7155\/jgaa.00178","volume":"13","author":"C Bentz","year":"2009","unstructured":"Bentz, C., Costa, M.-C., Picouleau, C., Ries, B., de Werra, D.: Degree-constrained edge partitioning in graphs arising from discrete tomography. J. Graph Algorithms Appl. 13(2), 99\u2013118 (2009)","journal-title":"J. Graph Algorithms Appl."},{"key":"2153_CR3","doi-asserted-by":"crossref","unstructured":"B\u00e9rczi, K., Kir\u00e1ly, Z., Liu, C., Miklos, I.: Packing tree degree sequences. Informatica 43(1) (2019)","DOI":"10.31449\/inf.v43i1.2675"},{"issue":"1","key":"2153_CR4","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1002\/jgt.20598","volume":"70","author":"A Busch","year":"2012","unstructured":"Busch, A., Ferrara, M., Hartke, S., Jacobson, M., Kaul, H., West, D.: Packing of graphic n-tuples. J. Graph Theory 70(1), 29\u201339 (2012)","journal-title":"J. Graph Theory"},{"issue":"2","key":"2153_CR5","doi-asserted-by":"publisher","first-page":"177","DOI":"10.1016\/0012-365X(88)90070-2","volume":"71","author":"Y-C Chen","year":"1988","unstructured":"Chen, Y.-C.: A short proof of Kundu\u2019s k-factor theorem. Discret. Math. 71(2), 177\u2013179 (1988)","journal-title":"Discret. Math."},{"key":"2153_CR6","first-page":"264","volume":"11","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., Gallai, T.: Graphs with vertices of prescribed degrees (in Hungarian). Mat. Lapok 11, 264\u2013274 (1960)","journal-title":"Mat. Lapok"},{"issue":"1","key":"2153_CR7","doi-asserted-by":"publisher","first-page":"23","DOI":"10.1016\/j.dam.2010.09.011","volume":"159","author":"F Gu\u00ed\u00f1ez","year":"2011","unstructured":"Gu\u00ed\u00f1ez, F., Matamala, F.M., Thomass\u00e9, S.: Realizing disjoint degree sequences of span at most two: a tractable discrete tomography problem. Discret. Appl. Math. 159(1), 23\u201330 (2011)","journal-title":"Discret. Appl. Math."},{"key":"2153_CR8","doi-asserted-by":"publisher","first-page":"144","DOI":"10.1016\/j.dam.2015.07.025","volume":"209","author":"A Hillebrand","year":"2016","unstructured":"Hillebrand, A., McDiarmid, C.: Colour degree matrices of graphs with at most one cycle. Discret. Appl. Math. 209, 144\u2013152 (2016)","journal-title":"Discret. Appl. Math."},{"issue":"4","key":"2153_CR9","doi-asserted-by":"publisher","first-page":"367","DOI":"10.1016\/0012-365X(73)90068-X","volume":"6","author":"S Kundu","year":"1973","unstructured":"Kundu, S.: The k-factor conjecture is true. Discret. Math. 6(4), 367\u2013376 (1973)","journal-title":"Discret. Math."},{"issue":"1","key":"2153_CR10","doi-asserted-by":"publisher","first-page":"103","DOI":"10.1137\/0126006","volume":"26","author":"S Kundu","year":"1974","unstructured":"Kundu, S.: Disjoint representation of tree realizable sequences. SIAM J. Appl. Math. 26(1), 103\u2013107 (1974)","journal-title":"SIAM J. Appl. Math."},{"key":"2153_CR11","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1137\/0128025","volume":"28","author":"S Kundu","year":"1975","unstructured":"Kundu, S.: Disjoint representation of three tree realizable sequences. SIAM J. Appl. Math. 28, 290\u2013302 (1975)","journal-title":"SIAM J. Appl. Math."},{"key":"2153_CR12","doi-asserted-by":"publisher","first-page":"3503","DOI":"10.1016\/j.dam.2008.03.033","volume":"156","author":"A Tripathi","year":"2008","unstructured":"Tripathi, A., Tyagi, H.: A simple criterion on degree sequences of graphs. Discret. Appl. Math. 156, 3503\u20133517 (2008)","journal-title":"Discret. Appl. Math."},{"key":"2153_CR13","doi-asserted-by":"publisher","first-page":"417","DOI":"10.1016\/S0012-365X(02)00886-5","volume":"265","author":"A Tripathi","year":"2003","unstructured":"Tripathi, A., Vijay, S.: A note on a theorem of Erd\u0151s & Gallai. Discret. Math. 265, 417\u2013420 (2003)","journal-title":"Discret. Math."},{"issue":"1\u20133","key":"2153_CR14","doi-asserted-by":"publisher","first-page":"293","DOI":"10.1016\/0012-365X(92)90152-6","volume":"105","author":"I\u00c9 Zverovich","year":"1992","unstructured":"Zverovich, I.\u00c9., Zverovich, V.\u00c9.: Contributions to the theory of graphic sequences. Discret. Math. 105(1\u20133), 293\u2013303 (1992)","journal-title":"Discret. Math."}],"container-title":["Graphs and Combinatorics"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02153-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/article\/10.1007\/s00373-020-02153-0\/fulltext.html","content-type":"text\/html","content-version":"vor","intended-application":"text-mining"},{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/s00373-020-02153-0.pdf","content-type":"application\/pdf","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2021,3,20]],"date-time":"2021-03-20T00:29:22Z","timestamp":1616200162000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/s00373-020-02153-0"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2020,3,20]]},"references-count":14,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2020,5]]}},"alternative-id":["2153"],"URL":"https:\/\/doi.org\/10.1007\/s00373-020-02153-0","relation":{},"ISSN":["0911-0119","1435-5914"],"issn-type":[{"type":"print","value":"0911-0119"},{"type":"electronic","value":"1435-5914"}],"subject":[],"published":{"date-parts":[[2020,3,20]]},"assertion":[{"value":"10 April 2017","order":1,"name":"received","label":"Received","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"13 January 2019","order":2,"name":"revised","label":"Revised","group":{"name":"ArticleHistory","label":"Article History"}},{"value":"20 March 2020","order":3,"name":"first_online","label":"First Online","group":{"name":"ArticleHistory","label":"Article History"}}]}}