Antipodal edge-colorings of hypercubes
Author(s) -
Douglas B. West,
Jenifer I. Wise
Publication year - 2018
Publication title -
discussiones mathematicae graph theory
Language(s) - English
Resource type - Journals
SCImago Journal Rank - 0.476
H-Index - 19
eISSN - 2083-5892
pISSN - 1234-3099
DOI - 10.7151/dmgt.2055
Subject(s) - antipodal point , combinatorics , hypercube , mathematics , enhanced data rates for gsm evolution , computer science , geometry , artificial intelligence
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.
Accelerating Research
Robert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom
Address
John Eccles HouseRobert Robinson Avenue,
Oxford Science Park, Oxford
OX4 4GP, United Kingdom