Finding 2-factors without triangles

Abstract: A 2-factor is a set of edges M of a graph G such that each vertex is incident to exactly two edges of M. Thus M determines a set of cycles in G.

One can efficiently compute minimum cost 2-factors in weighted graphs. It is open whether one can do the same, if we forbid triangles, i.e., each cycle has at least four edges. For the unweighted case, a complicated result of Hartvigsen shows that one can find such a 2-matching in polynomial time.

In the talk, we will review known results related to finding triangle free 2-factors, see its relation to the traveling salesman problem, and discuss several open problems.

Posted on Apr 18, 2019 in ACGO, Seminars