Home > RHUMJ > Vol. 20 (2019) > Iss. 1

#### Article Title

#### Abstract

The problem of finding a maximum matching on a bipartite graph is well-understood and can be solved using the augmenting path algorithm. However, the similar problem of finding a large set of vertex-disjoint triangles on tripartite graphs has not received much attention. In this paper, we define a set of vertex-disjoint triangles as a “tratching.” The problem of finding a tratching that covers all vertices of a tripartite graph can be shown to be NP-complete using a reduction from the three-dimensional matching problem. In this paper, however, we introduce a new construction that allows us to emulate Boolean circuits using tripartite graphs in order to prove that covering a given vertex subset of a tripartite graph with a tratching is NP-hard, thereby attacking the tratching problem from a new angle.

#### Sponsor

Jeremy Martin

#### Recommended Citation

Bradshaw, Peter A.
(2019)
"Triangle Packing on Tripartite Graphs Is Hard,"
*Rose-Hulman Undergraduate Mathematics Journal*: Vol. 20
:
Iss.
1
, Article 7.

Available at:
https://scholar.rose-hulman.edu/rhumj/vol20/iss1/7