Strong Fractional Tuza's conjecture

From papers

Let GG be a graph, and let ν(G)\nu(G) be the maximum number of edge-disjoint triangles in GG. For kNk\in\mathbb{N}, a kk-multi-transversal is a multiset FE(G)F\subseteq E(G) such that every triangle of GG contains at least kk elements of FF. Define τk(G)\tau^*_k(G) to be the minimum of F/k|F|/k over all kk-multi-transversals FF.

Strong Fractional Tuza's conjecture. For every kNk\in\mathbb{N} with k2k\geq 2 and every graph GG,

τk(G)2ν(G).\tau^*_k(G)\leq 2\nu(G).

This strengthens the fractional inequality τ(G)2ν(G)\tau^*(G)\leq 2\nu(G) by requiring a bounded-denominator multi-transversal for every k2k\geq2. The fractional inequality is known, but the stated uniform bound for all such kk is posed as an open question.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Parinya Chalermsook, Samir Khuller, Pattara Sukprasert and Sumedha Uniyal, “Multi-transversals for Triangles and the Tuza's Conjecture”, arXiv:2001.00257 (2021).

Solutions 0

No solutions have been posted yet.