Linear forest

Isolated vertices are allowed, as are graphs with a single connected component. However, star graphs are not allowed as a subgraph (such as the claw in the second graph), and neither are cycles

In graph theory, a branch of mathematics, a linear forest is a kind of forest where each component is a path graph,Template:Rp or a disjoint union of nontrivial paths.Template:Rp Equivalently, it is an acyclic and claw-free graph.Template:Rp An acyclic graph where every vertex has degree 0, 1, or 2 is a linear forest.Template:RpTemplate:Rp An undirected graph has Colin de Verdière graph invariant at most 1 if and only if it is a (node-)disjoint union of paths, i.e. it is linear.Template:RpTemplate:Rp Any linear forest is a subgraph of the path graph with the same number of vertices.Template:Rp

Extensions to the notation

According to Habib and Peroche, a k-linear forest consists of paths of k or fewer nodes each.Template:Rp

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.Template:Rp

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.Template:Rp

Derived concepts

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 $\mathrm{\Delta }$, the linear arboricity is always at least $\lceil \mathrm{\Delta }/2\rceil$, and it is conjectured that it is always at most $\lfloor (\mathrm{\Delta }+1)/2\rfloor$.

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 ${\mathrm{\Delta }}^{3/2}$, and there exist graphs for which it is at least proportional to this quantity.