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

About 2 years old · traced to

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 n≥n0n\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.

References

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).

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.