{"id":"arxiv/2608.29902","url":"https://arxiv.org/abs/2608.29902","tags":["cs.GT","cs.DM","math.CO"],"score":0,"title":"Fair Division of Graphs: Beyond Traceability","domain":"cs.GT","source":"arxiv","authors":["Nicolas Bousquet","Frank Connor","Agnès Totschnig","Sébastien Zeitoun"],"reviews":0,"subject":"cs.GT","summary":"In this paper, we study fair division problems in which resources are structured as graphs and agents must receive connected bundles. This connectivity requirement fundamentally alters the problem, making it significantly more challenging than its classical counterpart. We focus on the fairness notion of $\\mathrm{EF1}_{\\mathrm{outer}}$, where envy can be eliminated by removing at most one vertex whose deletion does not disconnect the bundle -- a critical constraint for applications such as land division and network allocation. Our first result extends prior work by establishing the existence…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-08-30","reactions":{}}