Casselgren, Petros and Fufa's Cartesian-product edge-precoloring conjecture

From papers

Let GG be a graph, let τ\tau be a precoloring of some edges of GG, and let τ\tau be extendable if it extends to a proper edge-coloring with χ(G)\chi'(G) colors. Let GHG \square H denote the Cartesian product of graphs GG and HH.

Casselgren, Petros and Fufa's conjecture. If every precoloring of at most k<χ(G)k < \chi'(G) edges of GG can be extended to a proper χ(G)\chi'(G)-edge-coloring, then every precoloring of at most k+1k+1 edges of GK2G \square K_2 is extendable to a proper (χ(G)+1)(\chi'(G)+1)-edge-coloring of GK2G \square K_2.

This conjecture is presented as a far-reaching generalization of the hypercube extension result. It is known for trees, complete and complete bipartite graphs, and graphs with small maximum degree; the general case remains open.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Pál Bärnkopf and Ervin Győri, “Extending partial edge-colorings of bounded size in Cartesian products of graphs”, arXiv:2603.23139 (2026).

Solutions 0

No solutions have been posted yet.