{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T18:37:00Z","timestamp":1770921420889,"version":"3.50.1"},"publisher-location":"Cham","reference-count":35,"publisher":"Springer Nature Switzerland","isbn-type":[{"value":"9783032178008","type":"print"},{"value":"9783032178015","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-17801-5_41","type":"book-chapter","created":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:29Z","timestamp":1770918809000},"page":"563-577","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":0,"title":["Clique-Free t-Matchings in\u00a0Degree-Bounded Graphs"],"prefix":"10.1007","author":[{"given":"Katarzyna","family":"Paluch","sequence":"first","affiliation":[]},{"given":"Mateusz","family":"Wasylkiewicz","sequence":"additional","affiliation":[]}],"member":"297","published-online":{"date-parts":[[2026,2,13]]},"reference":[{"key":"41_CR1","doi-asserted-by":"crossref","unstructured":"Aggarwal, G., Goel, G., Karande, C., Mehta, A.: Online vertex-weighted bipartite matching and single-bid budgeted allocations. In: Proceedings of the Twenty-Second Annual ACM-SIAM Symposium on Discrete Algorithms, pp. 1253\u20131264. Society for Industrial and Applied Mathematics (2011)","DOI":"10.1137\/1.9781611973082.95"},{"issue":"3","key":"41_CR2","doi-asserted-by":"publisher","first-page":"565","DOI":"10.1016\/j.jctb.2011.08.007","volume":"102","author":"K B\u00e9rczi","year":"2012","unstructured":"B\u00e9rczi, K., Kobayashi, Y.: An algorithm for $$(n-3)$$-connectivity augmentation problem: jump system approach. J. Combin. Theo. Series B 102(3), 565\u2013587 (2012)","journal-title":"J. Combin. Theo. Series B"},{"key":"41_CR3","doi-asserted-by":"crossref","unstructured":"K.\u00a0B\u00e9rczi and L.\u00a0V\u00e9gh. Restricted b-matchings in degree-bounded graphs. In Integer Programming and Combinatorial Optimization, pp. 43\u201356 (2010)","DOI":"10.1007\/978-3-642-13036-6_4"},{"key":"41_CR4","unstructured":"Bosch-Calvo, M., Grandoni, F., Ameli, A.J.: A PTAS for triangle-free 2-matching. arXiv:2311.11869 (2023)"},{"issue":"1","key":"41_CR5","doi-asserted-by":"publisher","first-page":"17","DOI":"10.1137\/S0895480191222926","volume":"8","author":"A Bouchet","year":"1995","unstructured":"Bouchet, A., Cunningham, W.H.: Delta-matroids, jump systems, and bisubmodular polyhedra. SIAM J. Discret. Math. 8(1), 17\u201332 (1995)","journal-title":"SIAM J. Discret. Math."},{"key":"41_CR6","doi-asserted-by":"publisher","unstructured":"Chekuri, C., Ene, A., Vakilian, A.: Node-weighted network design in planar and minor-closed families of graphs. In: Czumaj, A., Mehlhorn, K., Pitts, A., Wattenhofer, R. (eds.) Automata. Languages, and Programming, pp. 206\u2013217. Springer, Berlin Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-31594-7_18","DOI":"10.1007\/978-3-642-31594-7_18"},{"issue":"2","key":"41_CR7","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1016\/0012-365X(80)90002-3","volume":"29","author":"G Cornu\u00e9jols","year":"1980","unstructured":"Cornu\u00e9jols, G., Pulleyblank, W.: A matching problem with side conditions. Discret. Math. 29(2), 135\u2013159 (1980)","journal-title":"Discret. Math."},{"key":"41_CR8","doi-asserted-by":"publisher","first-page":"515","DOI":"10.1007\/s101070100256","volume":"91","author":"W Cunningham","year":"2002","unstructured":"Cunningham, W.: Matching, matroids, and extensions. Math. Program. 91, 515\u2013542 (2002)","journal-title":"Math. Program."},{"key":"41_CR9","doi-asserted-by":"crossref","unstructured":"Fisher, M., Nemhauser, G., Wolsey, L.: An analysis of approximations for finding a maximum weight hamiltonian circuit. Oper. Res. 27(4), 799\u2013809 (1979)","DOI":"10.1287\/opre.27.4.799"},{"key":"41_CR10","doi-asserted-by":"crossref","unstructured":"Gabow, H.: An efficient reduction technique for degree-constrained subgraph and bidirected network flow problems. In: Proceedings of the Fifteenth Annual ACM Symposium on Theory of Computing, pp. 448\u2013456 (1983)","DOI":"10.1145\/800061.808776"},{"key":"41_CR11","unstructured":"Hartvigsen, D.: Extensions of Matching Theory. PhD thesis, Carnegie-Mellon University (1984)"},{"issue":"5","key":"41_CR12","doi-asserted-by":"publisher","first-page":"693","DOI":"10.1016\/j.jctb.2006.01.004","volume":"96","author":"D Hartvigsen","year":"2006","unstructured":"Hartvigsen, D.: Finding maximum square-free $$2$$-matchings in bipartite graphs. J. Combin. Theo. Series B 96(5), 693\u2013705 (2006)","journal-title":"J. Combin. Theo. Series B"},{"issue":"3","key":"41_CR13","doi-asserted-by":"publisher","first-page":"581","DOI":"10.1002\/jgt.23089","volume":"106","author":"D Hartvigsen","year":"2024","unstructured":"Hartvigsen, D.: Finding triangle-free 2-factors in general graphs. J. Graph Theory 106(3), 581\u2013662 (2024)","journal-title":"J. Graph Theory"},{"issue":"3","key":"41_CR14","doi-asserted-by":"publisher","first-page":"1027","DOI":"10.1137\/090760416","volume":"21","author":"D Hartvigsen","year":"2011","unstructured":"Hartvigsen, D., Li, Y.: Maximum cardinality simple 2-matchings in subcubic graphs. SIAM J. Optim. 21(3), 1027\u20131045 (2011)","journal-title":"SIAM J. Optim."},{"key":"41_CR15","doi-asserted-by":"publisher","first-page":"43","DOI":"10.1007\/s10107-012-0516-0","volume":"138","author":"D Hartvigsen","year":"2013","unstructured":"Hartvigsen, D., Li, Y.: Polyhedron of triangle-free simple 2-matchings in subcubic graphs. Math. Program. 138, 43\u201382 (2013)","journal-title":"Math. Program."},{"key":"41_CR16","unstructured":"Iwamasa, Y., Kobayashi, Y., Takazawa, K.: Finding a maximum restricted t-matching via boolean edge-CSP. In: 32nd Annual European Symposium on Algorithms, pp. 75:1\u201375:15 (2024)"},{"key":"41_CR17","volume-title":"Restricted $$t$$-Matchings Bipartite Graphs","author":"Z Kir\u00e1ly","year":"2009","unstructured":"Kir\u00e1ly, Z.: Restricted $$t$$-Matchings Bipartite Graphs. Technical report, Egerv\u00e1ry Research Group (2009)"},{"key":"41_CR18","doi-asserted-by":"publisher","first-page":"197","DOI":"10.1016\/j.disopt.2010.04.001","volume":"7","author":"Y Kobayashi","year":"2010","unstructured":"Kobayashi, Y.: A simple algorithm for finding a maximum triangle-free $$2$$-matching in subcubic graphs. Discret. Optim. 7, 197\u2013202 (2010)","journal-title":"Discret. Optim."},{"key":"41_CR19","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y.: Weighted triangle-free $$2$$-matching problem with edge-disjoint forbidden triangles. In: Integer Programming and Combinatorial Optimization, pp. 280\u2013293 (2020)","DOI":"10.1007\/978-3-030-45771-6_22"},{"key":"41_CR20","doi-asserted-by":"crossref","unstructured":"Kobayashi, Y., Noguchi, T.: Validating a PTAS for triangle-free 2-matching via a simple decomposition theorem. In 2025 Symposium on Simplicity in Algorithms, pp. 281\u2013289 (2025)","DOI":"10.1137\/1.9781611978315.22"},{"key":"41_CR21","doi-asserted-by":"publisher","first-page":"948","DOI":"10.1016\/j.jctb.2012.03.003","volume":"102","author":"Y Kobayashi","year":"2012","unstructured":"Kobayashi, Y., Szabo, J., Takazawa, K.: A proof of Cunningham\u2019s conjecture on restricted subgraphs and jump systems. J. Combin. Theo. Series B 102, 948\u2013966 (2012)","journal-title":"J. Combin. Theo. Series B"},{"issue":"2","key":"41_CR22","doi-asserted-by":"publisher","first-page":"98","DOI":"10.1016\/j.disopt.2012.02.003","volume":"9","author":"Y Kobayashi","year":"2012","unstructured":"Kobayashi, Y., Yin, X.: An algorithm for finding a maximum t-matching excluding complete partite subgraphs. Discret. Optim. 9(2), 98\u2013108 (2012)","journal-title":"Discret. Optim."},{"key":"41_CR23","doi-asserted-by":"crossref","unstructured":"Lov\u00e1sz, L., Plummer, M.: Matching theory. AMS Chelsea Publishing, corrected reprint of the 1986 original edition (2009)","DOI":"10.1090\/chel\/367"},{"key":"41_CR24","doi-asserted-by":"publisher","first-page":"349","DOI":"10.1137\/060652282","volume":"21","author":"M Makai","year":"2007","unstructured":"Makai, M.: On maximum cost $$K_{t, t}$$-free $$t$$-matchings of bipartite graphs. SIAM J. Discret. Math. 21, 349\u2013360 (2007)","journal-title":"SIAM J. Discret. Math."},{"key":"41_CR25","unstructured":"Nam, Y.: Matching Theory: Subgraphs with Degree Constraints and other Properties. PhD thesis, University of British Columbia (1994)"},{"key":"41_CR26","unstructured":"Paluch, K.: Triangle-free 2-matchings. arXiv:2311.13590 (2023)"},{"key":"41_CR27","unstructured":"Paluch, K., Elbassioni, K., van Zuylen, A.: Simpler approximation of the maximum asymmetric traveling salesman problem. In 29th International Symposium on Theoretical Aspects of Computer Science, pp. 501\u2013506 (2012)"},{"key":"41_CR28","unstructured":"Paluch, K., Wasylkiewicz, M.: Restricted $$t$$-matchings via half-edges. In: 29th Annual European Symposium on Algorithms, pp. 73:1\u201373:17 (2021)"},{"key":"41_CR29","doi-asserted-by":"crossref","unstructured":"Paluch,K., Wasylkiewicz, M.: A simple combinatorial algorithm for restricted 2-matchings in subcubic graphs - via half-edges. Inform. Process. Lett. 171 (2021)","DOI":"10.1016\/j.ipl.2021.106146"},{"key":"41_CR30","unstructured":"Paluch, K., Wasylkiewicz, M.: Clique-free t-matchings in degree-bounded graphs. arXiv:2405.00429 (2024). https:\/\/doi.org\/10.48550\/arXiv.2405.00429"},{"key":"41_CR31","doi-asserted-by":"publisher","first-page":"57","DOI":"10.1007\/s10107-006-0053-9","volume":"110","author":"G Pap","year":"2007","unstructured":"Pap, G.: Combinatorial algorithms for matchings, even factors and square-free 2-factors. Math. Program. 110, 57\u201369 (2007)","journal-title":"Math. Program."},{"key":"41_CR32","doi-asserted-by":"crossref","unstructured":"Svensson, O.: Approximating $$ATSP$$ by relaxing connectivity. In: 56th Annual Symposium on Foundations of Computer Science, pp. 1\u201319 (2015)","DOI":"10.1109\/FOCS.2015.10"},{"issue":"2","key":"41_CR33","doi-asserted-by":"publisher","first-page":"351","DOI":"10.1287\/moor.1080.0365","volume":"34","author":"K Takazawa","year":"2009","unstructured":"Takazawa, K.: A weighted $$K_{t, t}$$-free $$t$$-factor algorithm for bipartite graphs. Math. Oper. Res. 34(2), 351\u2013362 (2009)","journal-title":"Math. Oper. Res."},{"issue":"2","key":"41_CR34","doi-asserted-by":"publisher","first-page":"695","DOI":"10.1137\/100787507","volume":"25","author":"L V\u00e9gh","year":"2011","unstructured":"V\u00e9gh, L.: Augmenting undirected node-connectivity by one. SIAM J. Discret. Math. 25(2), 695\u2013718 (2011)","journal-title":"SIAM J. Discret. Math."},{"key":"41_CR35","unstructured":"Vornberger, O.: Easy and hard cycle covers. Technical report, Universit\u00e4t Paderborn (1980)"}],"container-title":["Lecture Notes in Computer Science","SOFSEM 2026: Theory and Practice of Computer Science"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-032-17801-5_41","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,2,12]],"date-time":"2026-02-12T17:53:32Z","timestamp":1770918812000},"score":1,"resource":{"primary":{"URL":"https:\/\/link.springer.com\/10.1007\/978-3-032-17801-5_41"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2026]]},"ISBN":["9783032178008","9783032178015"],"references-count":35,"URL":"https:\/\/doi.org\/10.1007\/978-3-032-17801-5_41","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":"13 February 2026","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"SOFSEM","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on Current Trends in Theory and Practice of Computer Science","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Krakow","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Poland","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":"9 February 2026","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"13 February 2026","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"51","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"sofsem2026","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/sofsem.uj.edu.pl\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}}]}}