Ryser–Lovász conjecture for monochromatic tree covers

Let GG be a graph, let r-obreakcoloringsr\text{-} obreak\text{colorings} denote edge-colorings of GG with rr colors, and let tcr(G)\mathrm{tc}_r(G) be the minimum number of monochromatic connected subgraphs whose vertex sets cover V(G)V(G) in every such coloring. Let alpha(G)alpha(G) be the independence number of GG.

Ryser–Lovász conjecture. For every integer r2r\geq 2 and every graph GG,

tcr(G)(r1)α(G).\mathrm{tc}_r(G)\leq (r-1)\alpha(G).

The conjecture is best possible when r1r-1 is a prime power. It is known for r=2,3r=2,3 and for complete graphs when r5r\leq 5, but remains open for r4r\geq 4 in general.

Sources & referencesView supporting material

Primary source

Deepak Bal and Louis DeBiasio, “Partitioning random graphs into monochromatic components”, arXiv:1509.09168 (2017).

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.