Kouider–Lonc's balanced path-decomposition conjecture

About 10 years old · traced to

Let ℓ\ell be a positive integer, and let PℓP_\ell be the path with ℓ\ell edges. A balanced PℓP_\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 2ℓ2\ell-regular, then GG admits a balanced PℓP_\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.

References

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.