Antipodal Edge-Colorings of Hypercubes

Abstract

Two vertices of the k-dimensional hypercube Qkare antipodal if they differ in every coordinate. Edges uv and xy are antipodal if u is antipodal to x and v is antipodal to y. An antipodal edge-coloring of Qkis a 2- edge-coloring such that antipodal edges always have different colors. Norine conjectured that for k ≥ 2, in every antipodal edge-coloring of Qksome two antipodal vertices are connected by a monochromatic path. Feder and Subi proved this for k ≤ 5. We prove it for k ≤ 6.

Keywords

• antipodal edge-coloring
• hypercube
• monochromatic geodesic
• 05c55
• 05c38