Packing and covering cliques in graphs (Spring 2021)

A triangle packing in a graph G is a set of triangles in G that do not share any edge. Pick the largest such packing and suppose it has k triangles in it. Now we want to make the graph triangle free by deleting some number of edges, and would like to understand precisely how many as a function of k.

We need to delete at least k edges (one from each triangle in the largest packing). And if we delete the 3k edges in the largest packing, then we would have deleted all possible triangles (otherwise it wouldn’t have been the largest packing). A conjecture known as Tuza’s Conjecture says that we can do better, in that deleting 2k edges should always be enough!

We will explore variants of this conjecture. Specifically, we will try to understand what we can say in the situation where triangles are replaced by K_4, the complete graph on four vertices.

For more information contact Abdul Basit (abasit@iastate.edu).

People:

• Abdul Basit (Postdoc)

• Shira Zerbib (Faculty)

• Daniel McGinnis (Grad)

Pre-requisites:

• Experience with proofs (in courses or research projects)

• Experience with combinatorics (Math 304) is desirable, but not necessary