Linear arboricity

In graph theory, a branch of mathematics, the linear arboricity of an undirected graph is the smallest number of linear forests its edges can be partitioned into. Here, a linear forest is an acyclic graph with maximum degree two, i.e., a disjoint union of path graphs.

Unsolved problem in mathematics: Does every graph of maximum degree $\Delta$ have linear arboricity at most ${\displaystyle \lfloor (\Delta +1)/2\rfloor }$? (more unsolved problems in mathematics)

The linear arboricity of a graph $G$ with maximum degree $\Delta$ is always at least ${\displaystyle \lceil \Delta /2\rceil }$, because each linear forest can use only two of the edges at a maximum-degree vertex. The linear arboricity conjecture of Akiyama, Exoo & Harary (1981) is that this lower bound is also tight: according to their conjecture, every graph has linear arboricity at most ${\displaystyle \lfloor (\Delta +1)/2\rfloor }$.^[1] However, this remains unproven, with the best proven upper bound on the linear arboricity being somewhat larger, ${\displaystyle \Delta /2+O(\Delta ^{2/3}(\log \Delta )^{1/3})}$.^[2]

In a regular graph, the linear arboricity cannot equal $\Delta/2$ because the endpoints of each path in one of the linear forests would not have two adjacent edges used by that forest. Therefore, for regular graphs, the linear arboricity conjecture implies that the linear arboricity is exactly ${\displaystyle \lfloor (\Delta +1)/2\rfloor }$.

Linear arboricity is a variation of arboricity, the minimum number of forests that the edges of a graph can be partitioned into. Researchers have also studied linear k-arboricity, a variant of linear arboricity in which each path in the linear forest can have at most k edges.^[2] Unlike arboricity, which can be determined in polynomial time, linear arboricity is NP-hard. Even recognizing the graphs of linear arboricity two is NP-complete.^[3] However, for cubic graphs and other graphs of maximum degree three, the linear arboricity is always two, and a decomposition into two linear forests can be found in linear time using an algorithm based on depth-first search.^[4]

References

1. Akiyama, Jin; Exoo, Geoffrey; Harary, Frank (1981), "Covering and packing in graphs. IV. Linear arboricity", Networks, 11 (1): 69–72, doi:10.1002/net.3230110108, MR 608921.
2. Alon, Noga; Teague, V. J.; Wormald, N. C. (2001), "Linear arboricity and linear k-arboricity of regular graphs", Graphs and Combinatorics, 17 (1): 11–16, doi:10.1007/PL00007233, MR 1828624.
3. Shermer, Thomas C. (1996), "On rectangle visibility graphs. III. External visibility and complexity" (PDF), Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pp. 234–239.
4. Duncan, Christian A.; Eppstein, David; Kobourov, Stephen G. (2004), "The geometric thickness of low degree graphs", Proc. 20th ACM Symposium on Computational Geometry (SoCG 2004), pp. 340–346, arXiv:cs.CG/0312056, doi:10.1145/997817.997868.