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

From papers

Let GG be a graph, let m1m\geq 1 and k2k\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 ww' is uniform on II when the weights assigned by ww' 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 ww' 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.

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

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

Solutions 0

No solutions have been posted yet.