2023/03/09 by Carl Johan Casselgren, Casselgren, Carl Johan, Fikre Bogale Petros +3
Computer Science · #Advanced Graph Theory Research #Combinatorics (math.CO) #FOS: Mathematics
paper · pdf · doi:10.48550/arxiv.2303.05507
openalex publication_date 2023/03/09 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28
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 χ'(G)-edge coloring, then every precoloring of at most k+1 edges of G \square K2 is extendable to a proper (χ'(G) +1)-edge coloring of G \square K2. 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.