Path-pairable Cartesian products of two non-path-pairable graphs
Let and be graphs, and let 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 and such that
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
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.