Cartesian-product edge-precoloring conjecture for two graphs

Let GG and HH be graphs. Suppose every precoloring of at most k<χ(G)k < \chi'(G) edges of GG extends to a proper edge-coloring with \chi'(G) colors, and every precoloring of at most l<χ(H)l < \chi'(H) edges of HH extends to a proper edge-coloring with \chi'(H) colors. Let GHG \square H denote their Cartesian product.

General Cartesian-product conjecture. Every precoloring of at most k+l+1k+l+1 edges of GHG \square H is extendable to a proper (χ(G)+χ(H))(\chi'(G)+\chi'(H))-edge-coloring of GHG \square H.

This is proposed as a far-reaching generalization of the preceding conjecture and would resolve numerous open problems about edge-precoloring extension in Cartesian products. The paper establishes initial cases, while the general statement remains open.

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).

Additional references

8 papers in this index state this conjecture (2014–2026). The statement above is taken from the most recent of them; the others are arXiv:2510.07036, arXiv:2104.11910, arXiv:1708.02414, arXiv:1507.01818, arXiv:1507.04800, arXiv:1504.05987, arXiv:1407.5235.

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.