Linear forest

In graph theory, a branch of mathematics, a linear forest is a kind of forest formed from the disjoint union of path graphs. It is an undirected graph with no cycles in which every vertex has degree at most two. Linear forests are the same thing as claw-free forests. They are the graphs whose Colin de Verdière graph invariant is at most 1.^[1]

The linear arboricity of a graph is the minimum number of linear forests into which the graph can be partitioned. For a graph of maximum degree $\Delta$, the linear arboricity is always at least ${\displaystyle \lceil \Delta /2\rceil }$, and it is conjectured that it is always at most ${\displaystyle \lfloor (\Delta +1)/2\rfloor }$.^[2]

A linear coloring of a graph is a proper graph coloring in which the induced subgraph formed by each two colors is a linear forest. The linear chromatic number of a graph is the smallest number of colors used by any linear coloring. The linear chromatic number is at most proportional to ${\displaystyle \Delta ^{3/2}}$, and there exist graphs for which it is at least proportional to this quantity.^[3]

References

1. van der Holst, Hein; Lovász, László; Schrijver, Alexander (1999), "The Colin de Verdière graph parameter", Graph Theory and Combinatorial Biology (Balatonlelle, 1996), Bolyai Soc. Math. Stud., 7, Budapest: János Bolyai Math. Soc., pp. 29–85.
2. Alon, N. (1988), "The linear arboricity of graphs", Israel Journal of Mathematics, 62 (3): 311–325, doi:10.1007/BF02783300, MR 955135.
3. Yuster, Raphael (1998), "Linear coloring of graphs", Discrete Mathematics, 185 (1-3): 293–297, doi:10.1016/S0012-365X(97)00209-4, MR 1614290.