•  
  •  
 

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.

Author Bio

Peter Bradshaw attended the University of Kansas from 2012 to 2016. He received a Bachelor of Science in mathematics, and he wrote this article during his final semester. He has taught mathematics in Zhengzhou, China for two years, and he will begin a master's program at Simon Fraser University in September of 2018.

Download

Share

COinS