Path-pairable Cartesian products of two non-path-pairable graphs

At least 11 years old · documented by

Let GG and HH be graphs, and let G□HG\square H denote their Cartesian product. A graph is path-pairable if every pairing of distinct vertices can be joined by pairwise edge-disjoint paths.

Cartesian-product conjecture. There exist non-path-pairable graphs GG and HH such that

G□HG\square H

is path-pairable.

The Cartesian product of two path-pairable graphs need not be path-pairable, so this conjecture asks whether path-pairability of either factor is necessary at all for path-pairability of the product. The source describes this as an open question and states that the proposed condition is believed not to be necessary.

References

Primary source

Gabor Meszaros, “On Path-Pairability of Cartesian Product of Complete Bipartite Graphs”, arXiv:1401.7929 (2015).

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.