Fair splitting into arbitrarily many stable sets for colored paths

About 9 years old · traced to

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 q−1q-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 q−1q-1 in each VjV_j, with sizes differing by at most one, and satisfying

∣Si∩Vj∣≥⌊∣Vj∣+1q⌋−1|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.

References

Primary source

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

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.