Home » Subject » Combinatorics » Ramsey Theory
Importance: Medium ✭✭
Author(s): Norine, Serguei
Subject: Combinatorics
» Ramsey Theory
Keywords: antipodal
cube
edge-coloring
Recomm. for undergrads: no
Posted by: mdevos
on: October 6th, 2008

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.

This conjecture has been verified by hand for $ d \le 5 $.

Bibliography



* indicates original appearance(s) of problem.
5 comments

Reply

Comments are limited to a maximum of 1000 characters.
More information about formatting options