Open Problem Garden

Importance: Medium ✭✭

Author(s):

Subject:	Graph Theory
	» Extremal Graph Theory

Keywords:

Recomm. for undergrads: no

Posted	by:	fhavet
	on:	March 6th, 2013

Conjecture If $G$ has at most $k$ edge-disjoint triangles, then there is a set of $2k$ edges whose deletion destroys every triangle.

This conjecture may be rephrased in terms of packing and edge-transversal. A triangle packing is a set of pairwise edge-disjoint triangles. A triangle edge-tranversal is a set of edges meeting all triangles. Denote the maximum size of a triangle packing in $G$ by $\nu(G)$ and the minimum size of a triangle edge-transversal of $G$ by $\tau(G)$ . Clearly $\nu(G) \leq \tau(G)$ . The conjecture translates in $\tau(G)\leq 2\nu(G)$ .

This conjecture, if true, is best possible as can be seen by taking, say $G=K_4$ or $G=K_5$ . Trivially, $\tau(G)\leq 3\nu(G)$ , since the set of edges of a maximum triangle packing is a triangle edge-transversal. Haxell [H] proved that $\tau(G) \leq (3-\frac{3}{23})\nu(G)$ edges whose deletion destroys every triangle.

As usual, one can define fractional packing and fractional transversal. Let ${\cal T}$ be the set of triangles of $G$ . A fractional triangle packing is a function $f:{\cal T}\rightarrow \mathbb{R}^+$ such that $\sum_{T\ni e} \leq 1$ for every edge $e$ . A fractional triangle edge-transversal is a function $g:E\rightarrow \mathbb{R}^+$ such that $\sum_{e\in T} g(e)\geq 1$ for every triangle $T\in {\cal T}$ . We denote by $\nu^*(G)$ the maximum of $\sum_{T\in {\cal T}} f(T)$ over all fractional triangle packing and by $\tau^*(G)$ the minimum of $\sum_{e\in E(G)} g(e)$ over all fractional edge-transversals. By duality of linear programming $\tau^*(G) = \nu^*(G)$ . Krivelevich [K] proved two fractional versions of the conjecture: