Kouider–Lonc's balanced path-decomposition conjecture
Kouider–Lonc's balanced path-decomposition conjecture
Let be a positive integer, and let be the path with edges. A balanced -decomposition of a graph is a path decomposition in which every vertex is the end-vertex of exactly two paths.
Kouider–Lonc's conjecture. If is -regular, then admits a balanced -decomposition.
This strengthens the tree-decomposition conjecture for paths. Kouider and Lonc proved the statement when the girth satisfies , while the paper verifies it for paths of length ; 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
Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.
Solutions 0
Sign in to submit a solution.
No solutions have been posted yet.