Extremal Aspects of the Erdős--Gallai--Tuza Conjecture

Abstract

Erdős, Gallai, and Tuza posed the following problem: given an $n$-vertex graph $G$, let ${\tau }_1(G)$ denote the smallest size of a set of edges whose deletion makes $G$ triangle-free, and let ${\alpha }_1(G)$ denote the largest size of a set of edges containing at most one edge from each triangle of $G$. Is it always the case that ${\alpha }_1(G)+{\tau }_1(G)\le n^2/4$? We also consider a variant on this conjecture: if ${\tau }_B(G)$ is the smallest size of an edge set whose deletion makes $G$ bipartite, does the stronger inequality ${\alpha }_1(G)+{\tau }_B(G)\le n^2/4$ always hold? By considering the structure of a minimal counterexample to each version of the conjecture, we obtain two main results. Our first result states that any minimum counterexample to the original Erdős--Gallai--Tuza Conjecture has "dense edge cuts", and in particular has minimum degree greater than $n/2$. This implies that the conjecture holds for all graphs if and only if it holds for all triangular graphs (graphs where every edge lies in a triangle). Our second result states that ${\alpha }_1(G)+{\tau }_B(G)\le n^2/4$ whenever $G$ has no induced subgraph isomorphic to $K_4^{-}$, the graph obtained from the complete graph $K_4$ by deleting an edge. Thus, the original conjecture also holds for such graphs.

5 pages. Updated with journal reference, expanded background, and a few other minor changes