{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:59:11Z","timestamp":1780783151243,"version":"3.54.1"},"publisher-location":"Cham","reference-count":26,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032277312","type":"print"},{"value":"9783032277329","type":"electronic"}],"license":[{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"tdm","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"},{"start":{"date-parts":[[2026,1,1]],"date-time":"2026-01-01T00:00:00Z","timestamp":1767225600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.springernature.com\/gp\/researchers\/text-and-data-mining"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2026]]},"DOI":"10.1007\/978-3-032-27732-9_8","type":"book-chapter","created":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:48Z","timestamp":1780780488000},"page":"103-117","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Degree Realization with\u00a0Maximum Matching"],"prefix":"10.1007","author":[{"given":"Amotz","family":"Bar-Noy","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Igor","family":"Kalinichev","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"David","family":"Peleg","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Dror","family":"Rawitz","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"297","published-online":{"date-parts":[[2026,6,7]]},"reference":[{"issue":"1","key":"8_CR1","doi-asserted-by":"publisher","first-page":"112","DOI":"10.1016\/0196-6774(85)90022-7","volume":"6","author":"RP Anstee","year":"1985","unstructured":"Anstee, R.P.: An algorithmic proof of Tutte\u2019s $$f$$-factor theorem. J. Alg. 6(1), 112\u2013131 (1985)","journal-title":"J. Alg."},{"issue":"1\u20132","key":"8_CR2","doi-asserted-by":"publisher","first-page":"29","DOI":"10.1016\/0166-218X(90)90126-W","volume":"27","author":"RP Anstee","year":"1990","unstructured":"Anstee, R.P.: Simplified existence theorems for $$(g, f)$$-factors. Discr. Appl. Math. 27(1\u20132), 29\u201338 (1990)","journal-title":"Discr. Appl. Math."},{"key":"8_CR3","unstructured":"Bar-Noy, A., Kalinichev, I., Peleg, D., Rawitz, D.: Degree realization with minimum dominating set. In: 27th IPCO (2026, to appear)"},{"key":"8_CR4","doi-asserted-by":"publisher","first-page":"2146","DOI":"10.1016\/j.disc.2016.03.012","volume":"339","author":"MD Barrus","year":"2016","unstructured":"Barrus, M.D.: On realization graphs of degree sequences. Discr. Math. 339, 2146\u20132152 (2016)","journal-title":"Discr. Math."},{"issue":"6","key":"8_CR5","doi-asserted-by":"publisher","first-page":"1687","DOI":"10.1016\/j.disc.2019.02.005","volume":"342","author":"F Bock","year":"2019","unstructured":"Bock, F., Rautenbach, D.: On matching numbers of tree and bipartite degree sequences. Discr. Math. 342(6), 1687\u20131695 (2019)","journal-title":"Discr. Math."},{"issue":"2","key":"8_CR6","doi-asserted-by":"publisher","first-page":"154","DOI":"10.1016\/0095-8956(78)90016-3","volume":"24","author":"V Chungphaisan","year":"1978","unstructured":"Chungphaisan, V.: Construction of Hamiltonian graphs and bigraphs with prescribed degrees. J. Comb. Theory B 24(2), 154\u2013163 (1978)","journal-title":"J. Comb. Theory B"},{"key":"8_CR7","first-page":"264","volume":"11","author":"P Erd\u0151s","year":"1960","unstructured":"Erd\u0151s, P., Gallai, T.: Graphs with prescribed degrees of vertices [Hungarian]. Mat. Lapok (N.S.) 11, 264\u2013274 (1960)","journal-title":"Mat. Lapok (N.S.)"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"366","DOI":"10.1017\/S0963548313000096","volume":"22","author":"PL Erdos","year":"2013","unstructured":"Erdos, P.L., Kiraly, Z., Miklos, I.: On the swap-distances of different realizations of a graphical degree sequence. Comb. Probab. Comput. 22, 366\u2013383 (2013)","journal-title":"Comb. Probab. Comput."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Erd\u00f6s, P.L., Kharel, S.R., Mezei, T.R., Toroczkai, Z.: New results on graph matching from degree-preserving growth. Mathematics 12(22) (2024)","DOI":"10.3390\/math12223518"},{"key":"8_CR10","doi-asserted-by":"publisher","first-page":"166","DOI":"10.4153\/CJM-1965-016-2","volume":"17","author":"DR Fulkerson","year":"1965","unstructured":"Fulkerson, D.R., Hoffman, A.J., McAndrew, M.H.: Some properties of graphs with multiple edges. Canad. J. Math. 17, 166\u2013177 (1965)","journal-title":"Canad. J. Math."},{"key":"8_CR11","doi-asserted-by":"publisher","first-page":"831","DOI":"10.2140\/pjm.1960.10.831","volume":"12","author":"D Fulkerson","year":"1960","unstructured":"Fulkerson, D.: Zero-one matrices with zero trace. Pacific J. Math. 12, 831\u2013836 (1960)","journal-title":"Pacific J. Math."},{"key":"8_CR12","doi-asserted-by":"publisher","first-page":"181","DOI":"10.1016\/j.dam.2016.01.040","volume":"206","author":"M Gentner","year":"2016","unstructured":"Gentner, M., Henning, M.A., Rautenbach, D.: Largest domination number and smallest independence number of forests with given degree sequence. Discr. Appl. Math. 206, 181\u2013187 (2016)","journal-title":"Discr. Appl. Math."},{"issue":"1","key":"8_CR13","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1002\/jgt.22189","volume":"88","author":"M Gentner","year":"2018","unstructured":"Gentner, M., Henning, M.A., Rautenbach, D.: Smallest domination number and largest independence number of graphs and forests with given degree sequence. J. Graph Theory 88(1), 131\u2013145 (2018)","journal-title":"J. Graph Theory"},{"key":"8_CR14","unstructured":"Gould, R.J., Jackson, M.S., Lehel, J.: Potentially $$g$$-graphical degree sequences. In: Combinatorics, Graph Theory, and Algorithms, vol. 1, pp. 451\u2013460 (1999)"},{"issue":"3","key":"8_CR15","doi-asserted-by":"publisher","first-page":"496","DOI":"10.1137\/0110037","volume":"10","author":"SL Hakimi","year":"1962","unstructured":"Hakimi, S.L.: On realizability of a set of integers as degrees of the vertices of a linear graph - I. SIAM J. Appl. Math. 10(3), 496\u2013506 (1962)","journal-title":"SIAM J. Appl. Math."},{"key":"8_CR16","first-page":"477","volume":"80","author":"V Havel","year":"1955","unstructured":"Havel, V.: A remark on the existence of finite graphs. Casopis Pest. Mat. 80, 477\u2013480 (1955)","journal-title":"Casopis Pest. Mat."},{"key":"8_CR17","unstructured":"K\u00e9zdy, A., Lehel, J.: Degree sequences of graphs with prescribed clique size. In: Graph Theory, Combinatorics, Algorithms, and Applications, pp. 535\u2013544 (1998)"},{"key":"8_CR18","doi-asserted-by":"publisher","first-page":"79","DOI":"10.1016\/0012-365X(73)90037-X","volume":"6","author":"DJ Kleitman","year":"1973","unstructured":"Kleitman, D.J., Wang, D.L.: Algorithms for constructing graphs and digraphs with given valences and factors. Discr. Math. 6, 79\u201388 (1973)","journal-title":"Discr. Math."},{"issue":"4","key":"8_CR19","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. Discr. Math. 6(4), 367\u2013376 (1973)","journal-title":"Discr. Math."},{"issue":"1","key":"8_CR20","doi-asserted-by":"publisher","first-page":"41","DOI":"10.1016\/0012-365X(74)90108-3","volume":"8","author":"S Kundu","year":"1974","unstructured":"Kundu, S.: A factorization theorem for a certain class of graphs. Discr. Math. 8(1), 41\u201347 (1974)","journal-title":"Discr. Math."},{"issue":"2","key":"8_CR21","doi-asserted-by":"publisher","first-page":"173","DOI":"10.1016\/0012-365X(74)90147-2","volume":"9","author":"S Kundu","year":"1974","unstructured":"Kundu, S.: Generalizations of the $$k$$-factor theorem. Discr. Math. 9(2), 173\u2013179 (1974)","journal-title":"Discr. Math."},{"key":"8_CR22","doi-asserted-by":"crossref","unstructured":"Orlin, J.B.: Max flows in $$o(nm)$$ time, or better. In: 45th STOC, pp. 765\u2013774 (2013)","DOI":"10.1145\/2488608.2488705"},{"key":"8_CR23","unstructured":"Rao, A.R.: The clique number of a graph with a given degree sequence. ISI Lect. Notes 4, 251\u2013267 (1979)"},{"key":"8_CR24","doi-asserted-by":"publisher","first-page":"185","DOI":"10.1016\/0095-8956(72)90055-X","volume":"13","author":"AR Rao","year":"1972","unstructured":"Rao, A.R., Rao, S.B.: On factorable degree sequences. J. Comb. Theoey B 13, 185\u2013191 (1972)","journal-title":"J. Comb. Theoey B"},{"issue":"21","key":"8_CR25","doi-asserted-by":"publisher","first-page":"2485","DOI":"10.1016\/j.disc.2011.07.024","volume":"311","author":"JH Yin","year":"2011","unstructured":"Yin, J.H.: A Rao-type characterization for a sequence to have a realization containing a split graph. Discr. Math. 311(21), 2485\u20132489 (2011)","journal-title":"Discr. Math."},{"key":"8_CR26","doi-asserted-by":"crossref","unstructured":"Yin, J.H.: A short constructive proof of A. R. Rao\u2019s characterization of potentially $$k_{r+1}$$-graphic sequences. Discr. Appl. Math. 160(3), 352\u2013354 (2012)","DOI":"10.1016\/j.dam.2011.10.015"}],"container-title":["Lecture Notes in Computer Science","Combinatorial Algorithms"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-27732-9_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,6,6]],"date-time":"2026-06-06T21:14:50Z","timestamp":1780780490000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-27732-9_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032277312","9783032277329"],"references-count":26,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-27732-9_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"value":"0302-9743","type":"print"},{"value":"1611-3349","type":"electronic"}],"subject":[],"published":{"date-parts":[[2026]]},"assertion":[{"value":"7 June 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"The authors have no competing interests to declare that are relevant to the content of this article.","order":1,"name":"Ethics","group":{"name":"EthicsHeading","label":"Disclosure of Interests"}},{"value":"IWOCA","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Workshop on Combinatorial Algorithms","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Clermont-Ferrand","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2026","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"8 June 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"11 June 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"37","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"iwoca2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/iwoca2026.limos.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}