The weighted clique-packing conjecture for uniform weights on a clique independent set
The weighted clique-packing conjecture for uniform weights on a clique independent set
Let be a graph, let and , and let be an -weighting of . A -clique independent set is a set of vertices such that every -clique of contains exactly one vertex of . An -weighting is uniform on when the weights assigned by to the vertices of are equal. Weighted clique-packing conjecture. There exist a -clique independent set of and an -weighting of uniform on such that
for every -weighting of . The preceding theorems establish the analogous minimization statement for several graph classes, while the theorem for shows that uniformity on all vertices need not attain the minimum; the conjecture proposes that uniformity on a suitable -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
Sign in to submit a solution.
No solutions have been posted yet.