The triangle-free 2-matching polytope of subcubic graphs

The triangle-free 2-matching polytope of subcubic graphs⋆ Kristóf Bérczi⋆⋆ Abstract: The problem of determining the maximum size of a Ck-free 2-matching (that is, a 2-matching not containing cycles of length k) is a much studied question of matching theory. Cornuéjols and Pulleyblank showed that deciding the existence of a Ck-free 2-factor is NP-complete for k ≥ 5, while Hartvigsen gave an algorithm for the triangle-free case (k = 3). The existence of a C4-free 2-matching is still open. The description of the Ck-free 2-matching polytope is also of interest. Király showed that finding a maximum weight square-free 2-factor is NP-complete even in bipartite graphs with 0 − 1 weights, hence we should not expect a nice polyhedral description for k ≥ 4. However, imposing the condition that the graph has maximum degree 3, these problems become considerably easier. The polyhedral description of the triangle-free 2-factor and 2-matching polytopes of subcubic simple graphs was given by Hartvigsen and Li. In this paper, we give slight generalizations of their nice results by using a shrinking method inspired by Edmonds ’ maximum matching algorithm. Considering the general case, a new class of valid inequalities for the triangle-free 2-matching polytope is introduced. With the help of these inequalities, we propose a conjecture for the polyhedral description of the triangle-free 2-matching polytope of simple graphs.