Kouider–Lonc's balanced path-decomposition conjecture

Let \ell be a positive integer, and let PP_\ell be the path with \ell edges. A balanced PP_\ell-decomposition of a graph GG is a path decomposition in which every vertex is the end-vertex of exactly two paths.

Kouider–Lonc's conjecture. If GG is 22\ell-regular, then GG admits a balanced PP_\ell-decomposition.

This strengthens the tree-decomposition conjecture for paths. Kouider and Lonc proved the statement when the girth satisfies g(+3)/2g\geq(\ell+3)/2, while the paper verifies it for paths of length 44; the general assertion is not resolved in the supplied text.

Sources & referencesView supporting material

Primary source

Fábio Botler and Alexandre Talon, “Decomposing 8-regular graphs into paths of length 4”, arXiv:1607.01456 (2016).

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.