2010/03/13 by Maxim A. Babenko, Babenko, Maxim, Alexey Gusakov +3 · 1 citation
Computer Science · Mathematics · #Advanced Graph Theory Research #Combinatorics (math.CO) #Complexity and Algorithms in Graphs #FOS: Mathematics #Limits and Structures in Graph Theory
paper · pdf · doi:10.48550/arxiv.1003.2697
openalex publication_date 2010/03/13 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
A 2-matching in an undirected graph G = (VG, EG) is a function f \colon EG → \set0,1,2 such that for each node v ∈ VG the sum of values f(e) on all edges e incident to v does not exceed~2. The size of f is the sum ∑e f(e). If \sete ∈ EG | f(e) ≠ 0 contains no triangles then f is called triangle-free. Cornuéjols and Pulleyblank devised a combinatorial O(mn)-algorithm that finds a triangle free 2-matching of maximum size (hereinafter n := \absVG, m := \absEG) and also established a min-max theorem. We claim that this approach is, in fact, superfluous by demonstrating how their results may be obtained directly from the Edmonds--Gallai decomposition. Applying the algorithm of Micali and Vazirani we are able to find a maximum triangle-free 2-matching in O(m√(n))-time. Also we give a short self-contained algorithmic proof of the min-max theorem. 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 ≥ 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 + n3/2)-algorithm for d = 2k (k ≥ 2), and an O(n2)-algorithm for d = 2k + 1 (k ≥ 2). We also prove that there exists a constant c > 1 such that every 3-regular graph contains at least cn perfect triangle-free 2-matchings.