Distance-3 precoloring extension conjecture for graph products with an edge
Distance-3 precoloring extension conjecture for graph products with an edge
Let be a graph with maximum degree , and let be the complete graph on two vertices. Consider the Cartesian product . 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 are prescribed colors from a set of at most colors, and the distance between any two precolored edges is at least , then the precoloring is extendable. The paper presents this as an open question concerning whether the preceding theorem holds for every graph ; 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
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.