Finding triangle‐free 2‐factors in general graphs
- 8 March 2024
- journal article
- research article
- Published by Wiley in Journal of Graph Theory
- Vol. 106 (3) , 581-662
Abstract
A 2‐factor in a graph is a subset of edges such that every node of is incident with exactly two edges of . Many results are known concerning 2‐factors including a polynomial‐time algorithm for finding 2‐factors and a characterization of those graphs that have a 2‐factor. The problem of finding a 2‐factor in a graph is a relaxation of the NP‐hard problem of finding a Hamilton cycle. A stronger relaxation is the problem of finding a triangle‐free 2‐factor, that is, a 2‐factor whose edges induce no cycle of length 3. In this paper, we present a polynomial‐time algorithm for the problem of finding a triangle‐free 2‐factor as well as a characterization of the graphs that have such a 2‐factor and related min–max and augmenting path theorems.Keywords
This publication has 36 references indexed in Scilit:
- Improved Algorithms for Even Factors and Square-Free Simple b-MatchingsAlgorithmica, 2012
- Polyhedron of triangle-free simple 2-matchings in subcubic graphsMathematical Programming, 2012
- Combinatorial algorithms for matchings, even factors and square-free 2-factorsMathematical Programming, 2006
- Matching, matroids, and extensionsMathematical Programming, 2002
- Restricted 2-factor polytopesMathematical Programming, 2000
- A matching problem with side conditionsDiscrete Mathematics, 1980
- Vertex packings: Structural properties and algorithmsMathematical Programming, 1975
- Maximum-Minimum Sätze über GraphenActa Mathematica Hungarica, 1958
- On factorisation of graphsActa Mathematica Hungarica, 1950
- Die Theorie der regulären graphsActa Mathematica, 1891