Distance-3 precoloring extension conjecture for graph products with an edge

Let GG be a graph with maximum degree Δ(G)\Delta(G), and let K2K_2 be the complete graph on two vertices. Consider the Cartesian product GK2G\square K_2. A precoloring is extendable if it extends to a proper edge coloring using the prescribed color set. Graph–edge product conjecture. If some edges of GK2G\square K_2 are prescribed colors from a set of at most Δ(G)+1\Delta(G)+1 colors, and the distance between any two precolored edges is at least 33, then the precoloring is extendable. The paper presents this as an open question concerning whether the preceding theorem holds for every graph GG; the supplied text gives no evidence that it has been resolved.

Sources & referencesView supporting material

Primary source

Pál Bärnkopf and Ervin Győri, “Extending edge colorings of distance-3 matchings in the Cartesian product of graphs”, arXiv:2310.09973 (2026).

Progress summary

Never refreshed

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

Solutions 0

No solutions have been posted yet.