Fair splitting into arbitrarily many stable sets for colored paths
Let be a positive integer, and let be a path whose vertex set is partitioned into subsets , each of size at least . A subset of vertices is -stable if no two of its vertices are at distance less than , with distance counted in edges.
Fair stable-set splitting conjecture. There always exist pairwise disjoint -stable sets covering all vertices but in each , with sizes differing by at most one, and satisfying
for all and all .
This conjecture extends the paper's two-independent-set theorem to an arbitrary number of sets: when , -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
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.