  When allocating a set of indivisible items among agents, the ideal condition
of envy-freeness cannot always be achieved. Envy-freeness up to any good (EFX),
and envy-freeness with $k$ hidden items (HEF-$k$) are two very compelling
relaxations of envy-freeness, which remain elusive in many settings. We study a
natural relaxation of these two fairness constraints, where we place the agents
on the vertices of an undirected graph, and only require that our allocations
satisfy the EFX (resp. HEF) constraint on the edges of the graph. We refer to
these allocations as graph-EFX (resp. graph-HEF) or simply $G$-EFX (resp.
$G$-HEF) allocations. We show that for any graph $G$, there always exists a
$G$-HEF-$k$ allocation of goods, where $k$ is the size of a minimum vertex
cover of $G$, and that this is essentially tight. We show that $G$-EFX
allocations of goods exist for three different classes of graphs -- two of them
generalizing the star $K_{1, n-1}$ and the third generalizing the three-edge
path $P_4$. Many of these results extend to allocations of chores as well.
Overall, we show several natural settings in which the graph structure helps
obtain strong fairness guarantees. Finally, we evaluate an algorithm using
problem instances from Spliddit to show that $G$-EFX allocations appear to
exist for paths $P_n$, pointing the way towards showing EFX for even broader
families of graphs.
