Article ID | Journal | Published Year | Pages | File Type |
---|---|---|---|---|
5776929 | Discrete Mathematics | 2017 | 8 Pages |
Abstract
Feder and Subi conjectured that for any 2-coloring of the edges of the n-dimensional cube, there is an antipodal pair of vertices connected by a path that changes color at most once. They proved that if the coloring is such that there are no properly edge colored 4-cycles, the conjecture is true, without a color change. We generalize their theorem by weakening the assumption on the coloring. Our method can be applied to a similar question on any graph, if the condition on the coloring is satisfied. We solve the corresponding problem on the toroidal grid of size 2aÃ2b.
Related Topics
Physical Sciences and Engineering
Mathematics
Discrete Mathematics and Combinatorics
Authors
Daniel Soltész,