{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,5,13]],"date-time":"2024-05-13T15:52:38Z","timestamp":1715615558989},"reference-count":11,"publisher":"World Scientific Pub Co Pte Lt","issue":"04","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Discrete Math. Algorithm. Appl."],"published-print":{"date-parts":[[2010,12]]},"abstract":"<jats:p> A 2-matching in an undirected graph G = (VG, EG) is a function x: EG \u2192 {0, 1, 2} such that for each node v \u2208 VG the sum of values x(e) for all edges e incident to v does not exceed 2. The size of x is the sum \u2211<jats:sub>e<\/jats:sub> x(e). If {e \u2208 EG|x(e) \u2260 0} contains no triangles then x is called triangle-free. <\/jats:p><jats:p> Cornu\u00e9jols and Pulleyblank devised a combinatorial O(mn)-algorithm that finds a maximum triangle free 2-matching of size (hereinafter n \u2254 |VG|, m \u2254 |EG|) and also established a min-max theorem. <\/jats:p><jats:p> We claim that this approach is, in fact, superfluous by demonstrating how these results may be obtained directly from the Edmonds\u2013Gallai decomposition. Applying the algorithm of Micali and Vazirani we are able to find a maximum triangle-free 2-matching in [Formula: see text] time. Also we give a short self-contained algorithmic proof of the min-max theorem. <\/jats:p><jats:p> Next, we consider the case of regular graphs. It is well-known that every regular graph admits a perfect 2-matching. One can easily strengthen this result and prove that every d-regular graph (for d \u2265 3) contains a perfect triangle-free 2-matching. We give the following algorithms for finding a perfect triangle-free 2-matching in a d-regular graph: an O(n)-algorithm for d = 3, an O(m + n<jats:sup>3\/2<\/jats:sup>)-algorithm for d = 2k(k \u2265 2), and an O(n<jats:sup>2<\/jats:sup>)-algorithm for d = 2k + 1(k \u2265 2). <\/jats:p><jats:p> We also prove that there exists a constant c &gt; 1 such that every 3-regular graph contains at least c<jats:sup>n<\/jats:sup> perfect triangle-free 2-matchings. <\/jats:p>","DOI":"10.1142\/s1793830910000930","type":"journal-article","created":{"date-parts":[[2011,1,17]],"date-time":"2011-01-17T08:21:26Z","timestamp":1295252486000},"page":"643-654","source":"Crossref","is-referenced-by-count":3,"title":["TRIANGLE-FREE 2-MATCHINGS REVISITED"],"prefix":"10.1142","volume":"02","author":[{"given":"MAXIM","family":"BABENKO","sequence":"first","affiliation":[{"name":"Department of Mechanics and Mathematics, Moscow State University, Leninskie Gory, 119991 Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ALEXEY","family":"GUSAKOV","sequence":"additional","affiliation":[{"name":"Department of Mechanics and Mathematics, Moscow State University, Leninskie Gory, 119991 Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"ILYA","family":"RAZENSHTEYN","sequence":"additional","affiliation":[{"name":"Department of Mechanics and Mathematics, Moscow State University, Leninskie Gory, 119991 Moscow, Russia"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"219","published-online":{"date-parts":[[2012,4,6]]},"reference":[{"key":"rf1","doi-asserted-by":"publisher","DOI":"10.1007\/s004930170002"},{"key":"rf2","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0120901"},{"key":"rf3","doi-asserted-by":"publisher","DOI":"10.1007\/BF02579340"},{"key":"rf4","volume-title":"Graph Theory","author":"Diestel R.","year":"2005"},{"key":"rf5","doi-asserted-by":"publisher","DOI":"10.1137\/0202019"},{"key":"rf6","first-page":"279","volume":"7","author":"Lov\u00e1sz L.","journal-title":"Studia Scientiarum Mathematicarum Hungarica"},{"key":"rf7","volume-title":"Matching Theory","author":"Lov\u00e1sz L.","year":"1986"},{"key":"rf9","doi-asserted-by":"publisher","DOI":"10.1007\/BF02392606"},{"key":"rf10","doi-asserted-by":"publisher","DOI":"10.1007\/BFb0066196"},{"key":"rf11","volume-title":"Combinatorial Optimization","author":"Schrijver A.","year":"2003"},{"key":"rf12","first-page":"83","volume":"41","author":"Voorhoeve M.","journal-title":"Nederl. Akad. Wetensch. Indag. Math."}],"container-title":["Discrete Mathematics, Algorithms and Applications"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.worldscientific.com\/doi\/pdf\/10.1142\/S1793830910000930","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2019,8,6]],"date-time":"2019-08-06T17:16:12Z","timestamp":1565111772000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.worldscientific.com\/doi\/abs\/10.1142\/S1793830910000930"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,12]]},"references-count":11,"journal-issue":{"issue":"04","published-online":{"date-parts":[[2012,4,6]]},"published-print":{"date-parts":[[2010,12]]}},"alternative-id":["10.1142\/S1793830910000930"],"URL":"https:\/\/doi.org\/10.1142\/s1793830910000930","relation":{},"ISSN":["1793-8309","1793-8317"],"issn-type":[{"value":"1793-8309","type":"print"},{"value":"1793-8317","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,12]]}}}