Extending partial edge colorings of cartesian products of graphs

arXiv2303.05507MaRDI QIDQ6429015FDOQ6429015

Authors: Carl Johan Casselgren, Fikre B. Petros, Samuel Asefa Fufa 

Publication date: 9 March 2023

Abstract: We consider the problem of extending partial edge colorings of cartesian products of graphs. More specifically, we suggest the following Evans-type conjecture: If $G$ is a graph where every precoloring of at most $k$ precolored edges can be extended to a proper $ch{i}^{\prime }(G)$-edge coloring, then every precoloring of at most $k+1$ edges of $Gsquare{K}_2$ is extendable to a proper $(ch{i}^{\prime }(G)+1)$-edge coloring of $Gsquare{K}_2$. In this paper we verify that this conjecture holds for trees, complete and complete bipartite graphs, as well as for graphs with small maximum degree. We also prove versions of the conjecture for general regular graphs where the precolored edges are required to be independent.

This page was built for publication: Extending partial edge colorings of cartesian products of graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6429015)