We found a match
Your institution may have rights to this item. Sign in to continue.
- Title
Avoiding and Extending Partial Edge Colorings of Hypercubes.
- Authors
Casselgren, Carl Johan; Johansson, Per; Markström, Klas
- Abstract
We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring φ of the d-dimensional hypercube Q d , we are interested in whether there is a proper d-edge coloring of Q d that agrees with the coloring φ on every edge that is colored under φ ; or, similarly, if there is a proper d-edge coloring that disagrees with φ on every edge that is colored under φ . In particular, we prove that for any d ≥ 1 , if φ is a partial d-edge coloring of Q d , then φ is avoidable if every color appears on at most d/8 edges and the coloring satisfies a relatively mild structural condition, or φ is proper and every color appears on at most d - 2 edges. We also show that φ is avoidable if d is divisible by 3 and every color class of φ is an induced matching. Moreover, for all 1 ≤ k ≤ d , we characterize for which configurations consisting of a partial coloring φ of d - k edges and a partial coloring ψ of k edges, there is an extension of φ that avoids ψ .
- Publication
Graphs & Combinatorics, 2022, Vol 38, Issue 3, p1
- ISSN
0911-0119
- Publication type
Article
- DOI
10.1007/s00373-022-02485-z