On the structure of envy-free orientations on graphs

Fair division is the problem of allocating a set of items among agents in a fair manner. One of the most sought-after fairness notions is envy-freeness (EF), requiring that no agent envies another's allocation. When items are indivisible, it ceases to exist, and envy-freeness up to any good (EFX) emerged as one of its strongest relaxations. The existence of EFX allocations is arguably the biggest open question within fair division. Recently, Christodoulou, Fiat, Koutsoupias, and Sgouritsa (EC 2023) introduced showed that EFX allocations exist for the case of graphical valuations where an instance is represented by a graph: nodes are agents, edges are goods, and each agent values only her incident edges. On the other hand, they showed NP-hardness for checking the existence of EFX orientation where every edge is allocated to one of its incident vertices, and asked for a characterization of graphs that exhibit EFX orientation regardless of the assigned valuations. In this paper, we make significant progress toward answering their question. We introduce the notion of strongly EFX orientable graphs -- graphs that have EFX orientations regardless of how much agents value the edges. We show a surprising connection between this property and the chromatic number of the graph, namely $\chi(G)$ for graph $G$. In particular, we show that graphs with $\chi(G)\le 2$ are strongly EFX orientable, and those with $\chi(G)>3$ are not strongly EFX orientable. We provide examples of strongly EFX orientable and non-strongly EFX orientable graphs of $\chi(G)=3$ to prove tightness. Finally, we give a complete characterization of strong EFX orientability when restricted to binary valuations.