Exact anti-Ramsey number of vertex-disjoint triangles

Let kC3kC_3 denote the union of kk vertex-disjoint copies of the triangle C3C_3. For a positive integer nn, let ar(n,kC3)ar(n,kC_3) be the maximum number of colors in an edge-coloring of KnK_n containing no rainbow copy of kC3kC_3. Conjecture on vertex-disjoint triangles.

ar(n,kC3)=max{(3k12)+n3k+1,(nk+2)24+(k2)(nk+2)+(k22)+1}ar(n,kC_3)=\max\left\{\binom{3k-1}{2}+n-3k+1,\left\lfloor\frac{(n-k+2)^2}{4}\right\rfloor+(k-2)(n-k+2)+\binom{k-2}{2}+1\right\}

for all n3kn\geq 3k. The formula is known at n=3kn=3k and for all n2k2k+2n\geq 2k^2-k+2, while the intermediate range is the subject of the conjecture.

Sources & referencesView supporting material

Primary source

Fangfang Wu, Shenggui Zhang, Binlong Li and Jimeng Xiao, “Anti-Ramsey numbers for vertex-disjoint triangles”, arXiv:2201.03424 (2022).

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.