The weighted clique-packing conjecture for uniform weights on a clique independent set

At least 3 years old · documented by

Let GG be a graph, let m≥1m\geq 1 and k≥2k\geq 2, and let ww be an mm-weighting of GG. A kk-clique independent set is a set II of vertices such that every kk-clique of GG contains exactly one vertex of II. An mm-weighting w′w' is uniform on II when the weights assigned by w′w' to the vertices of II are equal. Weighted clique-packing conjecture. There exist a kk-clique independent set II of GG and an mm-weighting w′w' of GG uniform on II such that

πk(G(w′))≤πk(G(w)).\pi_k(G(w'))\leq\pi_k(G(w)).

for every mm-weighting ww of GG. The preceding theorems establish the analogous minimization statement for several graph classes, while the theorem for k=3k=3 shows that uniformity on all vertices need not attain the minimum; the conjecture proposes that uniformity on a suitable kk-clique independent set always suffices.

References

Primary source

Peter Borg, Carl Feghali and Rémi Pellerin, “Solution to a problem of Katona on counting cliques of weighted graphs”, arXiv:2211.04153 (2023).

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.