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.

The linear arboricity of any graph of maximum degree $\Delta$ is known to be at least $\lceil\Delta/2\rceil$ and is conjectured to be at most $\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

The linear arboricity of a graph $G$ with maximum degree $\Delta$ is always at least $\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 is that this lower bound is also tight: according to their conjecture, every graph has linear arboricity at most $\lceil(\Delta+1)/2\rceil$. However, this remains unproven, with the best proven upper bound on the linear arboricity being somewhat larger,
$\Delta/2 + O(\Delta^)$ for some constant $c> 0$ due to Ferber, Fox and Jain.

In order for the linear arboricity of a graph to equal $\Delta/2$, $\Delta$ must be even and each linear forest must have two edges incident to each vertex of degree $\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 $\Delta$. Thus, a graph whose linear arboricity equals $\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 $\Delta/2$. Therefore, for regular graphs, the linear arboricity conjecture implies that the linear arboricity is exactly $\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 -arboricity, a variant of linear arboricity in which each path in the linear forest can have at most edges.

Another related problem is Hamiltonian decomposition, the problem of decomposing a regular graph of even degree $\Delta$ into exactly $\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 $\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. 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.

References

{{reflist, refs=

{{citation
, last1 = Alon , first1 = Noga , author1-link = Noga Alon
, last2 = Teague , first2 = V. J. , author2-link = Vanessa Teague
, last3 = Wormald , first3 = N. C. , author3-link = Nick Wormald
, doi = 10.1007/PL00007233
, issue = 1
, journal = Graphs and Combinatorics
, mr = 1828624
, pages = 11–16
, title = Linear arboricity and linear {{mvar, k-arboricity of regular graphs
, volume = 17
, year = 2001.

{{citation
, last1 = Akiyama , first1 = Jin , author1-link = Jin Akiyama
, last2 = Exoo , first2 = Geoffrey
, last3 = Harary , first3 = Frank , author3-link = Frank Harary
, doi = 10.1002/net.3230110108
, issue = 1
, journal = Networks
, mr = 608921
, pages = 69–72
, title = Covering and packing in graphs. IV. Linear arboricity
, volume = 11
, year = 1981.

{{citation
, last1 = Duncan , first1 = Christian A.
, last2 = Eppstein , first2 = David , author2-link = David Eppstein
, last3 = Kobourov , first3 = Stephen G.
, arxiv = cs.CG/0312056
, contribution = The geometric thickness of low degree graphs
, doi = 10.1145/997817.997868
, pages = 340–346
, title = Proc. 20th ACM Symposium on Computational Geometry (SoCG 2004)
, year = 2004.

{{citation
, last1 = Ferber , first1 = Asaf
, last2 = Fox , first2 = Jacob , author2-link = Jacob Fox
, last3 = Jain , first3 = Vishesh
, arxiv = 1809.04716
, title = Towards the linear arboricity conjecture
, year = 2018.

{{citation
, last = Péroche , first = B.
, doi = 10.1016/0166-218X(84)90101-X
, issue = 2
, journal = Discrete Applied Mathematics
, mr = 743024
, pages = 195–208
, title = NP-completeness of some problems of partitioning and covering in graphs
, volume = 8
, year = 1984, doi-access = free
; see also {{citation
, last = Péroche , first = B.
, doi = 10.1051/ro/1982160201251
, issue = 2
, journal = RAIRO Recherche Opérationnelle
, mr = 679633
, pages = 125–129
, title = Complexité de l'arboricité linéaire d'un graphe
, volume = 16
, year = 1982, doi-access = free
and {{citation
, last = Péroche , first = B.
, doi = 10.1051/ro/1985190302931
, issue = 3
, journal = RAIRO Recherche Opérationnelle
, mr = 815871
, pages = 293–300
, title = Complexité de l'arboricité linéaire d'un graphe. II
, volume = 19
, year = 1985, doi-access = free
. A reduction of {{harvtxt, Péroche, 1982 from multigraphs to simple graphs is repeated in {{citation, first=Thomas C., last=Shermer, contribution=On rectangle visibility graphs. III. External visibility and complexity, title=Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96), pages=234–239, year=1996, contribution-url=http://www.cccg.ca/proceedings/1996/cccg1996_0039.pdf.

Graph invariants