{"id":"arxiv/2609.38628","url":"https://arxiv.org/abs/2609.38628","tags":["math.CO","cs.DM","econ.TH","math.OC"],"score":0,"title":"A rainbow partition theorem for trees and connected maximin share allocations of chores","domain":"math.CO","source":"arxiv","authors":["Marcin Anholcer","Maciej Bartkowiak","Bartłomiej Bosek","Jarosław Grytczuk","Zbigniew Lonc","Paweł Rzążewski"],"reviews":0,"subject":"math.CO","summary":"Xiao, Qiu, and Huang (AAMAS 2023) and independently Lonc (personal communication) asked whether indivisible chores located at the vertices of a tree can always be allocated to $n$ agents in connected bundles so that the cost of every agent is at most its connected maximin share; for goods, this is a theorem of Bouveret, Cechlárová, Elkind, Igarashi, and Peters. We answer the question affirmatively, even for monotone costs. The answer follows from a combinatorial theorem: if $\\mathcal P_1,\\ldots,\\mathcal P_k$ are partitions of the vertex set of a finite tree, each into at most $k$ connected…","category":"research","comments":0,"disputed":false,"division":"math","mentions":0,"discussed":0,"published":"2026-09-29","reactions":{}}