Distinct-color monochromatic partition and cover conjecture

Let GG be a graph on nn vertices and let r1r\geq 1. Write TCr\mathcal{T}\mathcal{C}_r for the property that every rr-edge-coloring of GG admits a cover by at most rr monochromatic connected subgraphs of distinct colors, and write TPr\mathcal{T}\mathcal{P}_r for the analogous partition property.

Distinct-color conjecture. If

δ(G)(112r)n,\delta(G)\geq \left(1-\frac{1}{2^r}\right)n,

then GG has property TCr\mathcal{T}\mathcal{C}_r (and property TPr\mathcal{T}\mathcal{P}_r).

The source notes that the statement is known for r=1r=1 and r=2r=2, and presents the general assertion as open; the cited example indicates that the minimum-degree bound would be best possible.

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.