antipodal


Edge-antipodal colorings of cubes ★★

Author(s): Norine

We let $Q_d$ denote the $d$-dimensional cube graph. A map $\phi : E(Q_d) \rightarrow \{0,1\}$ is called \emph{edge-antipodal} if $\phi(e) \neq \phi(e')$ whenever $e,e'$ are antipodal edges.

\begin{conjecture} If $d \ge 2$ and $\phi : E(Q_d) \rightarrow \{0,1\}$ is edge-antipodal, then there exist a pair of antipodal vertices $v,v' \in V(Q_d)$ which are joined by a monochromatic path. \end{conjecture}

Keywords: antipodal; cube; edge-coloring

Syndicate content