Gyárfás–Lehel biclique monochromatic-component conjecture

Let GG be a biclique, meaning a complete bipartite graph, whose edges are colored with rr colors. A monochromatic component is a connected component of the subgraph formed by the edges of one color.

Gyárfás–Lehel conjecture. In every rr-coloring of the edges of GG, the vertex set can be covered by the vertices of at most 2r22r-2 monochromatic components.

This is the bipartite analogue of the complete-graph monochromatic-component conjecture. The source notes that the bound is sharp, but does not state a resolution of the conjecture.

Sources & referencesView supporting material

Primary source

Luke Hawranick and Ruth Luo, “Covering complete r-partite hypergraphs with few monochromatic components”, arXiv:2603.04704 (2026).

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.