Linear forest

According to Habib and Peroche, a k-linear forest consists of paths of k or fewer nodes each.^[9]

According to Burr and Roberts, an (n, j)-linear forest has n vertices and j of its component paths have an odd number of vertices.^[2]

According to Faudree et al., a (k, t)-linear or (k, t, s)-linear forest has k edges, and t components of which s are single vertices; s is omitted if its value is not critical.^[10]

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 ${\displaystyle \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 }$.^[11]

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.^[12]