MathDB

Gyárfás's monochromatic component covering conjecture

At least 8 years old · documented by

Let KnK_n be the complete graph on vertex set [n]={1,2,…,n}[n]=\{1,2,\dots,n\}. Suppose its edges are coloured with kk colours. For A⊆[n]A\subseteq[n] and a colour cc, let Kn[A,c]K_n[A,c] denote the subgraph on AA consisting of the edges of colour cc.

Gyárfás's conjecture. For fixed kk, there exist sets A1,A2,…,Ak−1A_1,A_2,\dots,A_{k-1} whose union is [n][n], and colours c1,c2,…,ck−1c_1,c_2,\dots,c_{k-1}, such that Kn[Ai,ci]K_n[A_i,c_i] is connected for every i∈[k−1]i\in[k-1].

This is an important special case of the Lovász–Ryser conjecture, which predicts that a graph with independence number α(G)\alpha(G) can be covered by at most (k−1)α(G)(k-1)\alpha(G) monochromatic components in every kk-edge-colouring. The complete-graph case remains open for general kk (in particular, for k≥4k\geq4).

Equivalent formulations 1Other wordings

Other statements of this same problem, merged from separate entries. Each is equivalent to the statement above — proving any one settles them all.

  1. Gyárfás's monochromatic component covering conjecture

    Let GG be a complete 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's conjecture. In any coloring of the edges of GG with rr colors, the number of monochromatic components required to cover V(G)V(G) is at most r−1r-1. This conjecture is equivalent to the intersecting case of Ryser's conjecture for rr-partite, rr-uniform hypergraphs, and concerns covering all vertices of a complete graph by monochromatic connected components. Its resolution status is not established in the supplied text.

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

References

Primary source

Luka Milićević, “Covering complete graphs by monochromatically bounded sets”, arXiv:1705.09370 (2017).

covering-conjecturesgraph-coloringgraph-coloringshypergraph-coversmonochromatic-components
Posted

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.