Enomoto and Ota's path-partition conjecture

Let GG be a graph of order nn, let k3k\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+k1,\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 1ik1\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.

Sources & referencesView supporting material

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.