Partitioning the \(n\)-cube into sets with mutual distance 1 (Q1312006)

Assume that the vertices of the \(n\)-cube are partitioned in such a way that, given two subsets in the partition, there is always a vertex in one subset and a vertex in the other subset connected by an edge. Let \(m(n)\) be the maximal number of such subsets. In this paper it is proved that \((\sqrt 2/2)\sqrt{n2^ n}\leq m(n)\leq \sqrt{n2^ n}+ 1\). Furthermore, it is proposed to study the same problem for arbitrary graphs.