Triangle strings: Structures for augmentation of vertex-disjoint triangle sets

• Defining triangle strings, which correspond to the union of two triangle sets.
• An augmenting condition for maximum triangle sets based on triangle strings.
• An O(n)O(n) algorithm to judge a triangle string, and find out its maximum triangle set.
• A sufficient and necessary condition that a triangle string has a triangle factor.

Vertex-disjoint triangle sets (triangle sets for short) have been studied extensively. Many theoretical and computational results have been obtained. While the maximum triangle set problem can be viewed as the generalization of the maximum matching problem, there seems to be no parallel result to Berge's augmenting path characterization on maximum matching (C. Berge, 1957 [1]). In this paper, we describe a class of structures called triangle string, which turns out to be equivalent to the class of union of two triangle sets in a graph. Based on the concept of triangle string, a sufficient and necessary condition that a triangle set can be augmented is given. Furthermore, we provide an algorithm to determine whether a graph G with maximum degree 4 is a triangle string, and if G is a triangle string, we compute a maximum triangle set of it. Finally, we give a sufficient and necessary condition for a triangle string to have a triangle factor.