Abstract | ||
---|---|---|
In 2000, Enomoto and Ota conjectured that if a graph G satisfies \(\sigma _{2}(G) \ge |G| + k - 1\), then for any set of k vertices \(v_{1}, \ldots , v_{k}\) and for any positive integers \(n_{1}, \ldots , n_{k}\) with \(\sum n_{i} = |G|\), there exists a partition of V(G) into k paths \(P_{1}, \ldots , P_{k}\) such that \(v_{i}\) is an end of \(P_{i}\) and \(|P_{i}| = n_{i}\) for all i. We prove this conjecture when |G| is large. Our proof uses the Regularity Lemma along with several extremal lemmas, concluding with an absorbing argument to retrieve misbehaving vertices. |
Year | DOI | Venue |
---|---|---|
2018 | 10.1007/s00373-018-1956-y | Graphs and Combinatorics |
Keywords | DocType | Volume |
Path partition,Regularity lemma,Degree sum | Journal | 34 |
Issue | ISSN | Citations |
6 | 0911-0119 | 1 |
PageRank | References | Authors |
0.34 | 4 | 4 |
Name | Order | Citations | PageRank |
---|---|---|---|
Vincent Coll | 1 | 2 | 2.51 |
Alexander Halperin | 2 | 3 | 2.01 |
Colton Magnant | 3 | 113 | 29.08 |
Pouria Salehi Nowbandegani | 4 | 5 | 4.30 |