Akiyama's linear arboricity conjecture

About 7 years old · traced to

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.

References

Primary source

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

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.