Cartesian-product edge-precoloring conjecture for two graphs
Cartesian-product edge-precoloring conjecture for two graphs
Let and be graphs. Suppose every precoloring of at most edges of extends to a proper edge-coloring with \chi'(G) colors, and every precoloring of at most edges of extends to a proper edge-coloring with \chi'(H) colors. Let denote their Cartesian product.
General Cartesian-product conjecture. Every precoloring of at most edges of is extendable to a proper -edge-coloring of .
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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.