Edge-precoloring conjecture for Cartesian products with balanced complete bipartite graphs
Edge-precoloring conjecture for Cartesian products with balanced complete bipartite graphs
Let be an -regular, triangle-free graph, and let be the complete bipartite graph with parts of size . Let denote their Cartesian product.
Balanced complete-bipartite Cartesian-product conjecture. If any precoloring of at most edges of can be extended to a proper -edge-coloring of , then any precoloring of at most edges of can be extended to a proper -edge-coloring of .
This conjecture is suggested as a generalization beyond the cases already known for stars, even cycles, and trees. Its resolution, or the analogous statement for , would have implications for hypercube precoloring-extension problems; the conjecture 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
Sign in to submit a solution.
No solutions have been posted yet.