## The triangle-free 2-matching polytope of subcubic graphs

### Abstract

The problem of determining the maximum size of a \$C_k\$-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 \$C_k\$-free \$2\$-factor is NP-complete for \$k\ge 5\$, while Hartvigsen gave an algorithm for the triangle-free case (\$k=3\$). The existence of a \$C_4\$-free 2-matching is still open.

The description of the \$C_k\$-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\geq 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.

Bibtex entry:

@techreport{egres-12-02,
AUTHOR = {B{\'e}rczi, Krist{\'o}f},
TITLE = {The triangle-free 2-matching polytope of subcubic graphs},
NOTE= {{\tt www.cs.elte.hu/egres}},
INSTITUTION = {Egerv{\'a}ry Research Group, Budapest},
YEAR = {2012},
NUMBER = {TR-2012-02}
}