Gyárfás–Lehel conjecture for monochromatic tree covers

Let Kn,mK_{n,m} be the complete bipartite graph with parts of sizes nn and mm, and let tcr(Kn,m)\operatorname{tc}_r(K_{n,m}) be the minimum number of monochromatic trees whose vertices cover Kn,mK_{n,m} in every edge-colouring with at most rr colours. Gyárfás–Lehel conjecture. For all n,m1n,m\ge 1 and r2r\ge 2,

tcr(Kn,m)2r2.\operatorname{tc}_r(K_{n,m})\le 2r-2.

The conjecture is known for r5r\le 5, and examples show that the bound is sharp; the general case remains open.

Sources & referencesView supporting material

Primary source

Camila Fernández, Matías Pavez-Signé and Maya Stein, “Monochromatic partitions in 2-edge-coloured bipartite graphs”, arXiv:2403.12587 (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.