← All problems

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

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