2017/05/12 by Gregory J. Puleo, Puleo, Gregory J.
Mathematics · Computer Science · #Limits and Structures in Graph Theory #Advanced Graph Theory Research #Advanced Topology and Set Theory
paper · pdf · doi:10.48550/arxiv.1705.04745
Given a graph G, let τ1(G) denote the smallest size of a set of edges whose deletion makes G triangle-free, and let α1(G) denote the largest size of an edge set containing at most one edge from each triangle of G. Erdős, Gallai, and Tuza introduced several problems with the unifying theme that α1(G) and τ1(G) cannot both be "very large"; the most well-known such problem is their conjecture that α1(G) + τ1(G) ≤ |V(G)|2/4, which was proved by Norin and Sun. We consider three other problems within this theme (two introduced by Erdős, Gallai, and Tuza, another by Norin and Sun), all of which request an upper bound either on min\α1(G), τ1(G)\ or on α1(G) + kτ1(G) for some constant k, and prove the existence of graphs for which these quantities are "large".