Carl Johan Casselgren ; Jonas B. Granholm ; Fikre B. Petros - Extending partial edge colorings of iterated cartesian products of cycles and paths

dmtcs:11377 - Discrete Mathematics & Theoretical Computer Science, June 4, 2024, vol. 26:2 - https://doi.org/10.46298/dmtcs.11377
Extending partial edge colorings of iterated cartesian products of cycles and pathsArticle

Authors: Carl Johan Casselgren ; Jonas B. Granholm ; Fikre B. Petros

    We consider the problem of extending partial edge colorings of iterated cartesian products of even cycles and paths, focusing on the case when the precolored edges satisfy either an Evans-type condition or is a matching. In particular, we prove that if $G=C^d_{2k}$ is the $d$th power of the cartesian product of the even cycle $C_{2k}$ with itself, and at most $2d-1$ edges of $G$ are precolored, then there is a proper $2d$-edge coloring of $G$ that agrees with the partial coloring. We show that the same conclusion holds, without restrictions on the number of precolored edges, if any two precolored edges are at distance at least $4$ from each other. For odd cycles of length at least $5$, we prove that if $G=C^d_{2k+1}$ is the $d$th power of the cartesian product of the odd cycle $C_{2k+1}$ with itself ($k\geq2$), and at most $2d$ edges of $G$ are precolored, then there is a proper $(2d+1)$-edge coloring of $G$ that agrees with the partial coloring. Our results generalize previous ones on precoloring extension of hypercubes [Journal of Graph Theory 95 (2020) 410--444].


    Volume: vol. 26:2
    Section: Graph Theory
    Published on: June 4, 2024
    Accepted on: April 19, 2024
    Submitted on: May 25, 2023
    Keywords: Mathematics - Combinatorics

    Consultation statistics

    This page has been seen 76 times.
    This article's PDF has been downloaded 40 times.