Fair splitting of colored paths

MaRDI QIDQ2401427zbMATH OpenFDO

Authors Meysam Alishahi, Frédéric Meunier

Publication date 8 September 2017

Published in The Electronic Journal of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1704.02921, http://www.combinatorics.org/ojs/index.php/eljc/article/view/v24i3p41

IPFS File on IPFS (Hint: this is only the Hash - if you get a timeout, this file is not available on our server.)

zbMATH Keywords

independent setsnecklace splittingoctahedral Tucker lemma

Mathematics Subject Classification ID

Vertex subsets with special properties (dominating sets, independent sets, cliques, etc.) (05C69) Coloring of graphs and hypergraphs (05C15)

Abstract: 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 Ron Aharoni and coauthors. The proof uses the octahedral Tucker lemma. Our second result is the proof of a particular case of a conjecture of D{"o}m{"o}t{"o}r P{'a}lv{"o}lgyi about fair splittings of necklaces for which one can decide which thieves are advantaged. The proof is based on a rounding technique introduced by Noga Alon and coauthors to prove the discrete splitting necklace theorem from the continuous one.

Recommendations

• Splitting necklaces, with constraints
• Obstacles for splitting multidimensional necklaces
• Splitting necklaces
• Combinatorial necklace splitting
• scientific article; zbMATH DE number 496046

Cites work

• A combinatorical proof of Kneser's conjecture
• Algorithmic construction of sets for k -restrictions
• Combinatorial necklace splitting
• Combinatorial optimization. Polyhedra and efficiency (3 volumes)
• Fair representation by independent sets
• Generalized Kneser coloring theorems with combinatorial proofs
• Simplotopal maps and necklace splitting
• Splitting necklaces

Cited in

(6)

• Splitting loops and necklaces: variants of the square peg problem
• Fair representation in the intersection of two matroids
• The discrete yet ubiquitous theorems of Carathéodory, Helly, Sperner, Tucker, and Tverberg
• The structural complexity landscape of finding balance-fair shortest paths
• The complexity of finding fair independent sets in cycles
• Fair splittings by independent sets in sparse graphs

This page was built for publication: Fair splitting of colored paths

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2401427)