Bounded-endvertex path-packing conjecture for degenerate graphs

Let kk be a positive integer, let GG be a graph of degeneracy dd, and let ckc_k denote a constant depending on kk. A collection of paths is edge-disjoint if no two paths share an edge, and it is maximal if no further path of the specified length can be added while preserving edge-disjointness. Bounded-endvertex path-packing conjecture. There is a maximal collection C\mathcal{C} of edge-disjoint paths of length 2k2k in GG such that every vertex of GG is an endvertex of at most ckdc_kd paths in C\mathcal{C}. This is presented as an open question motivated by a proposition in the paper.

Sources & referencesView supporting material

Primary source

Zoltán Füredi, Ago-Erik Riet and Mykhaylo Tyomkyn, “Completing Partial Packings of Bipartite Graphs”, arXiv:1007.4287 (2010).

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.