Gyárfás–Lehel biclique monochromatic-component conjecture
Gyárfás–Lehel biclique monochromatic-component conjecture
Let be a biclique, meaning a complete bipartite graph, whose edges are colored with 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 -coloring of the edges of , the vertex set can be covered by the vertices of at most 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.