  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) 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 $\chi(G)$ of the 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.
