Enomoto and Ota's path-partition conjecture

About 12 years old · traced to

Let GG be a graph of order nn, let k≥3k\geq 3 be an integer, and let n1,…,nkn_{1},\dots,n_{k} be positive integers satisfying

∑i=1kni=n.\sum_{i=1}^{k}n_i=n.

Write σ2(G)\sigma_2(G) for the minimum degree sum of two nonadjacent vertices. Enomoto and Ota's conjecture. If

σ2(G)≥n+k−1,\sigma_2(G)\geq n+k-1,

then for any kk distinct vertices x1,…,xkx_1,\dots,x_k in GG, there exist vertex-disjoint paths P1,…,PkP_1,\dots,P_k such that ∣Pi∣=ni|P_i|=n_i and PiP_i starts at xix_i for every 1≤i≤k1\leq i\leq k. The conjecture predicts a prescribed path partition of the entire vertex set under a degree-sum condition; the paper proves it when the order of GG is sufficiently large, while the remaining cases are not addressed here.

References

Primary source

Vincent Coll, Alexander Halperin, Colton Magnant and Pouria Salehi Nowbandegani, “Enomoto and Ota's conjecture holds for large graphs”, arXiv:1408.0408 (2014).

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.