The proper rainbow triangle-packing conjecture for edge-colored graphs

At least 1 year old · documented by

Let GG be an edge-colored graph on nn vertices, let e(G)e(G) denote its number of edges, and let c(G)c(G) denote its number of colors. A proper mK3mK_3 is a collection of mm vertex-disjoint rainbow triangles. The proper rainbow triangle-packing conjecture. For every integer m≥1m\geq 1, if n≥5m+2n\geq 5m+2 and

e(G)+c(G)>(n2)+mn−(m+12),e(G)+c(G)>\binom{n}{2}+mn-\binom{m+1}{2},

then GG admits a proper mK3mK_3. This conjecture is motivated by constructions showing that the previously proposed bound with n≥5mn\geq 5m is false; the paper proves related sufficient conditions but leaves this sharper bound open.

References

Primary source

Jürgen Kritschgau, tahda queer, Cyrus Young and Wohua Zhou, “Note on vertex disjoint rainbow triangles in edge-colored graphs”, arXiv:2402.18053 (2024).

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.