Fair splitting into arbitrarily many stable sets for colored paths
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.
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
Sign in to submit a solution.
No solutions have been posted yet.