Fair splitting of colored paths (Q2401427): Difference between revisions

Summary: This paper deals with two problems about splitting fairly a path with colored vertices, where ``fairly'' means that each part contains almost the same amount of vertices in each color.{ }Our first result states that it is possible to remove one vertex per color from a path with colored vertices so that the remaining vertices can be fairly split into two independent sets of the path. It implies in particular a conjecture of \textit{R. Aharoni} et al. [``Fair representation by independent sets'', Preprint, \url{arXiv:1611.03196}]. The proof uses the octahedral Tucker lemma.{ }Our second result is the proof of a particular case of a conjecture of \textit{D. Pálvölgyi} [Electron. J. Comb. 16, No. 1, Research Paper R79, 8 p. (2009; Zbl 1186.05017)] about fair splittings of necklaces for which one can decide which thieves are advantaged. The proof is based on a rounding technique introduced by \textit{N. Alon} et al. [ACM Trans. Algorithms 2, No. 2, 153--177 (2006; Zbl 1321.68445)] to prove the discrete splitting necklace theorem from the continuous one.