Avoiding and Extending Partial Edge Colorings of Hypercubes

• Published in: Graphs and combinatorics 2022, Vol.38 (3), Article 79
• Main Authors: Casselgren, Carl Johan, Johansson, Per, Markström, Klas
• Format: Article
• Language: English
• Subjects: Avoiding edge coloring; Color; Coloring; Combinatorics; Edge coloring; Engineering Design; Hypercube; Hypercubes; Mathematics; Mathematics and Statistics; Original Paper; Precoloring extension
• ISSN: 0911-0119; 1435-5914; 1435-5914
• DOI: 10.1007/s00373-022-02485-z

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 ψ .