The spanning-coloring covering conjecture for complete partite hypergraphs

Let r3r\geq 3 and t1t\geq 1. A complete rr-uniform rr-partite hypergraph has its vertices partitioned into rr nonempty classes, with edges consisting of one vertex from each class. An edge-coloring is spanning if every vertex is incident to an edge of every color used. A monochromatic component is a connected component of the subhypergraph formed by the edges of one color, and let cov(r,k)\mathrm{cov}(r,k) be the maximum, over spanning kk-colorings, of the minimum number of monochromatic components needed to cover the vertex set.

The complete-partite covering conjecture.

cov(r,r+t)=t+1\mathrm{cov}(r,r+t)=t+1

for every r3r\geq 3 and t1t\geq 1.

The conjecture is proved for 1tr11\leq t\leq r-1, while for trt\geq r the paper proves only that t+2t+2 monochromatic components suffice; consequently the case corresponding to k2rk\geq 2r remains open.

Sources & referencesView supporting material

Primary source

András Gyárfás and Zoltán Király, “Covering complete partite hypergraphs by monochromatic components”, arXiv:1604.02791 (2016).

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.