On a Conjecture of Erdős, Gallai, and Tuza

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 have two main results. We first obtain the upper bound ${\alpha }_1(G)+{\tau }_1(G)\le 5n^2/16$, as a partial result towards the Erdős--Gallai--Tuza conjecture. We also show that always ${\alpha }_1(G)\le n^2/2-m$, where $m$ is the number of edges in $G$; this bound is sharp in several notable cases.

arXiv comment5 pages, minor revisions: added new details, new conjecture, and cleaned up notation slightly

Cited by in corpus (2)

• Extremal Aspects of the Erdős--Gallai--Tuza Conjecture
• A Note on Bipartite Subgraphs and Triangle-independent Sets