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
Degree may refer to:
As a unit of measurement
* Degree (angle), a unit of angle measurement
** Degree of geographical latitude
** Degree of geographical longitude
* Degree symbol (°), a notation used in science, engineering, and mathematics
...
at most two. Linear forests are the same thing as
claw-free In the Mathematics, mathematical and computer science field of cryptography, a group of three numbers (''x'',''y'',''z'') is said to be a claw of two permutations ''f''0 and ''f''1 if
:''f''0(''x'') = ''f''1(''y'') = ''z''.
A pair of permutations ...
forests. They are the graphs whose
Colin de Verdière graph invariant is at most 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
, the linear arboricity is always at least
, and it is conjectured that it is always at most
.
A linear coloring of a graph is a proper
graph coloring
In graph theory, graph coloring is a special case of graph labeling; it is an assignment of labels traditionally called "colors" to elements of a graph subject to certain constraints. In its simplest form, it is a way of coloring the vertices o ...
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.
[.]
References
{{reflist
Trees (graph theory)
Graph families