Explicit 3-colorings for exponential graphs

Adrien Argento, Pierre Charbit, Alantha Newman

For a graph $H$ and integer $k\ge 1$, two functions $f,g$ from $V(H)$ into $\{1,\dots ,k\}$ are adjacent if for all edges $uv$ of $H$, $f(u)\ne g(v)$. The graph of all such f…