Conjecture on the additive gap between integral and fractional tt-clique covers

From papers

For a graph GG, let CCt(G)\mathcal{C}\mathcal{C}_t(G) and CCt(G)\mathcal{C}\mathcal{C}^*_t(G) denote its integral and fractional tt-clique cover numbers, respectively. Additive-gap conjecture. For every ε>0\varepsilon>0 and every positive integer tt, there exists n0n_0 such that every graph GG on nn0n\geq n_0 vertices satisfies

CCt(G)CCt(G)+εnt.\mathcal{C}\mathcal{C}_t(G) \leq \mathcal{C}\mathcal{C}^*_t(G)+\varepsilon n^t.

The preceding argument establishes an analogous asymptotic statement for the decomposition number, but the supplied text gives no resolution of this clique-cover conjecture.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

József Balogh, Jialin He, Robert A. Krueger, The Nguyen and Michael C. Wigal, “Clique covers and decompositions of cliques of graphs”, arXiv:2412.05522 (2024).

Solutions 0

No solutions have been posted yet.