{"id":"arxiv/2607.01059","url":"https://arxiv.org/abs/2607.01059","tags":["cs.GT","cs.DS","math.CO"],"score":0,"title":"Fair Allocation under Conflict Constraints via Strong Colorability","domain":"cs.GT","source":"arxiv","authors":["Ishay Haviv"],"reviews":0,"subject":"cs.GT","summary":"In the fair allocation problem under conflict constraints, the goal is to partition the vertices of a graph among agents in a fair manner, such that no two adjacent vertices are assigned to the same agent. We study this problem for agents with common preferences through the lens of three fairness criteria: stochastic-dominance envy-freeness up to one item for preference orders (SD-EF1), envy-freeness up to one item for monotone additive valuations (EF1), and envy-freeness up to one item from each side for general additive valuations (EF[1,1]). To do so, we introduce a hierarchy of variants…","category":"research","comments":0,"disputed":false,"division":"cs","mentions":0,"discussed":0,"published":"2026-07-01","reactions":{}}