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; that is, it is a disjoint union of path graphs. Linear arboricity is a variant of arboricity, the minimum number of forests into which the edges can be partitioned.

Partition of the graph of a rhombic dodecahedron into two linear forests, showing that its linear arboricity is two

The linear arboricity of any graph of maximum degree ${\displaystyle \Delta }$ is known to be at least ${\displaystyle \lceil \Delta /2\rceil }$ and is conjectured to be at most ${\displaystyle \lceil (\Delta +1)/2\rceil }$. This conjecture would determine the linear arboricity exactly for graphs of odd degree, as in that case both expressions are equal. For graphs of even degree it would imply that the linear arboricity must be one of only two possible values, but determining the exact value among these two choices is NP-complete.

Relation to degree

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

The linear arboricity of a graph ${\displaystyle G}$ with maximum degree ${\displaystyle \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 \lceil (\Delta +1)/2\rceil }$.[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-c})}$ for some constant ${\displaystyle c>0}$ due to Ferber, Fox and Jain.[2]

In order for the linear arboricity of a graph to equal ${\displaystyle \Delta /2}$, ${\displaystyle \Delta }$ must be even and each linear forest must have two edges incident to each vertex of degree ${\displaystyle \Delta }$. But at a vertex that is at the end of a path, the forest containing that path has only one incident edge, so the degree at that vertex cannot equal ${\displaystyle \Delta }$. Thus, a graph whose linear arboricity equals ${\displaystyle \Delta /2}$ must have some vertices whose degree is less than maximum. In a regular graph, there are no such vertices, and the linear arboricity cannot equal ${\displaystyle \Delta /2}$. Therefore, for regular graphs, the linear arboricity conjecture implies that the linear arboricity is exactly ${\displaystyle \lceil (\Delta +1)/2\rceil }$.

Related problems

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.[3]

Another related problem is Hamiltonian decomposition, the problem of decomposing a regular graph of even degree ${\displaystyle \Delta }$ into exactly ${\displaystyle \Delta /2}$ Hamiltonian cycles. A given graph has a Hamiltonian decomposition if and only if the subgraph formed by removing an arbitrary vertex from the graph has linear arboricity ${\displaystyle \Delta /2}$.

Computational complexity

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.[4] However, for cubic graphs and other graphs of maximum degree three, the linear arboricity is always two,[1] and a decomposition into two linear forests can be found in linear time using an algorithm based on depth-first search.[5]

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 0608921.
2. Ferber, Asaf; Fox, Jacob; Jain, Vishesh (2018), Towards the linear arboricity conjecture, arXiv:1809.04716.
3. 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.
4. Péroche, B. (1984), "NP-completeness of some problems of partitioning and covering in graphs", Discrete Applied Mathematics, 8 (2): 195–208, doi:10.1016/0166-218X(84)90101-X, MR 0743024; see also Péroche, B. (1982), "Complexité de l'arboricité linéaire d'un graphe", RAIRO Recherche Opérationnelle, 16 (2): 125–129, doi:10.1051/ro/1982160201251, MR 0679633 and Péroche, B. (1985), "Complexité de l'arboricité linéaire d'un graphe. II", RAIRO Recherche Opérationnelle, 19 (3): 293–300, doi:10.1051/ro/1985190302931, MR 0815871. A reduction of Péroche (1982) from multigraphs to simple graphs is repeated in 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.
5. 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.