Fair splitting into arbitrarily many stable sets for colored paths

From papers

Let qq be a positive integer, and let PP be a path whose vertex set is partitioned into mm subsets V1,,VmV_1,\ldots,V_m, each of size at least q1q-1. A subset of vertices is qq-stable if no two of its vertices are at distance less than qq, with distance counted in edges.

Fair stable-set splitting conjecture. There always exist pairwise disjoint qq-stable sets S1,,SqS_1,\ldots,S_q covering all vertices but q1q-1 in each VjV_j, with sizes differing by at most one, and satisfying

SiVjVj+1q1|S_i\cap V_j|\geq \left\lfloor \frac{|V_j|+1}{q}\right\rfloor-1

for all i[q]i\in[q] and all j[m]j\in[m].

This conjecture extends the paper's two-independent-set theorem to an arbitrary number of sets: when q=2q=2, qq-stable sets are precisely independent sets. Its resolution is not given in the supplied text.

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

Meysam Alishahi and Frédéric Meunier, “Fair splitting of colored paths”, arXiv:1704.02921 (2017).

Solutions 0

No solutions have been posted yet.