Linear forest: Difference between revisions
imported>David Eppstein You do know that claw-free graph has a specific meaning that you could learn by reading the linked article? It means there is no K_{1,3} as an induced subgraph, not necessarily a component. If you have a vertex of degree ≥ 3, then either it and some two of its neighbors induce a triangle or it and any three of its neighbors induce a claw. And if all degrees ≤ 2 then either it is a linear forest or there is a cycle. So it is indeed equivalent. What was the star for? |
(No difference)
|
Latest revision as of 03:21, 9 February 2025
In graph theory, a branch of mathematics, a linear forest is a kind of forest where each component is a path graph,[1]Template:Rp or a disjoint union of nontrivial paths.[2]Template:Rp Equivalently, it is an acyclic and claw-free graph.[3]Template:Rp An acyclic graph where every vertex has degree 0, 1, or 2 is a linear forest.[4]Template:Rp[5]Template: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.[6]Template:Rp[7]Template:Rp Any linear forest is a subgraph of the path graph with the same number of vertices.[8]Template:Rp
Extensions to the notation
According to Habib and Peroche, a k-linear forest consists of paths of k or fewer nodes each.[9]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.[2]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.[10]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 , the linear arboricity is always at least , and it is conjectured that it is always at most .[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 , and there exist graphs for which it is at least proportional to this quantity.[12]