Home » Keyword index

antipodal


Combinatorics » Ramsey Theory

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 edge-antipodal if $ \phi(e) \neq \phi(e') $ whenever $ e,e' $ are antipodal edges.

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.

Keywords: antipodal; cube; edge-coloring

Posted by mdevos
updated August 20th, 2010
5 comments
Syndicate content