Extremal aspects of the Erdős-Gallai-Tuza conjecture

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 α1(G)+τB(G)≤n2/4 whenever G has no induced subgraph isomorphic to K4−, the graph obtained from the complete graph K4 by deleting an edge. Thus, the original conjecture also holds for such graphs.