Akiyama's linear arboricity conjecture

From papers

For a graph GG, a linear forest is a forest whose components are paths, and the linear arboricity la(G)la(G) is the minimum number of disjoint linear forests whose union contains all edges of GG. Let Δ\Delta be the maximum degree of GG.

Akiyama's linear arboricity conjecture. For every graph GG of maximum degree Δ\Delta,

la(G)Δ+12.la(G)\leq \left\lceil\frac{\Delta+1}{2}\right\rceil.

The conjecture was raised by Akiyama and collaborators and is presented in the paper as a central related problem. The supplied text gives no resolution status.

Progress summary

Nothing recorded yet. Refresh searches the literature and the public web for attempts on this problem, and writes the first summary here.

Sources & referencesView supporting material

Primary source

Uriel Feige and Ella Fuchs, “On the path partition number of 6-regular graphs”, arXiv:1911.08397 (2019).

Solutions 0

No solutions have been posted yet.