{"ID":5551603,"CreatedAt":"2026-07-02T01:54:51.863792489Z","UpdatedAt":"2026-07-04T15:13:22.648032999Z","DeletedAt":null,"paper_url":"https://arxiv.org/abs/2607.01059","arxiv_id":"2607.01059","title":"Fair Allocation under Conflict Constraints via Strong Colorability","abstract":"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 of the strong chromatic number, a graph quantity introduced independently by Alon and Fellows in the early nineties. Our results reveal a close connection between fair allocation under conflict constraints and the first two levels of this hierarchy, providing a unified route to both existential and algorithmic results. For SD-EF1, we fully characterize the number of agents needed to guarantee a fair allocation of a given graph for every common preference order. For EF1 and EF[1,1], we provide analogous sufficient conditions, extending a result on path graphs due to Equbal, Gurjar, Igarashi, Kumar, Manurangsi, Nath, Saxena, Vaish, and Yoneda. We also show that, unlike in the SD-EF1 setting, the sufficient conditions for EF1 and EF[1,1] are not necessary in general. Our framework yields existential and algorithmic consequences in terms of the maximum degree. We obtain that every graph with maximum degree $Δ$ admits SD-EF1, EF1, and EF[1,1] allocations for common preferences whenever the number of agents is at least $3Δ-1$. We further provide, for any $\\varepsilon\u003e0$, deterministic polynomial-time algorithms that find such allocations whenever the number of agents is at least $(3+\\varepsilon)Δ$. These guarantees strengthen earlier work by Barman and Viswanathan on equitable colorings.","short_abstract":"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-d...","url_abs":"https://arxiv.org/abs/2607.01059","url_pdf":"https://arxiv.org/pdf/2607.01059v1","authors":"[\"Ishay Haviv\"]","published":"2026-07-01T15:22:32Z","proceeding":"cs.GT","tasks":"[\"cs.GT\",\"cs.DS\",\"math.CO\"]","methods":"[\"LoRA\"]","has_code":false}