{
  "id": "2104.00716",
  "version": "v1",
  "published": "2021-04-01T18:50:30.000Z",
  "updated": "2021-04-01T18:50:30.000Z",
  "title": "Avoiding and extending partial edge colorings of hypercubes",
  "authors": [
    "Carl Johan Casselgren",
    "Per Johansson",
    "Klas Markström"
  ],
  "categories": [
    "math.CO"
  ],
  "abstract": "We consider the problem of extending and avoiding partial edge colorings of hypercubes; that is, given a partial edge coloring $\\varphi$ 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 $\\varphi$ on every edge that is colored under $\\varphi$; or, similarly, if there is a proper $d$-edge coloring that disagrees with $\\varphi$ on every edge that is colored under $\\varphi$. In particular, we prove that for any $d\\geq 1$, if $\\varphi$ is a partial $d$-edge coloring of $Q_d$, then $\\varphi$ is avoidable if every color appears on at most $d/8$ edges and the coloring satisfies a relatively mild structural condition, or $\\varphi$ is proper and every color appears on at most $d-2$ edges. We also show that the same conclusion holds if $d$ is divisible by $3$ and every color class of $\\varphi$ is an induced matching. Moreover, for all $1 \\leq k \\leq d$, we characterize for which configurations consisting of a partial coloring $\\varphi$ of $d-k$ edges and a partial coloring $\\psi$ of $k$ edges, there is an extension of $\\varphi$ that avoids $\\psi$.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2021-04-01T18:50:30.000Z"
    }
  ],
  "analyses": {
    "keywords": [
      "extending partial edge colorings",
      "color appears",
      "avoiding partial edge colorings",
      "relatively mild structural condition",
      "partial coloring"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 0,
      "language": "en",
      "license": "arXiv",
      "status": "editable"
    }
  }
}