Strong Fractional Tuza's conjecture

At least 5 years old · documented by

Let GG be a graph, and let ν(G)\nu(G) be the maximum number of edge-disjoint triangles in GG. For k∈Nk\in\mathbb{N}, a kk-multi-transversal is a multiset F⊆E(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 k∈Nk\in\mathbb{N} with k≥2k\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 k≥2k\geq2. The fractional inequality is known, but the stated uniform bound for all such kk is posed as an open question.

References

Primary source

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

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.