Linear forest explained

In graph theory, a branch of mathematics, a linear forest is a kind of forest where each component is a path graph,[1] or a disjoint union of nontrivial paths.[2] Equivalently, it is an acyclic and claw-free graph.[3] An acyclic graph where every vertex has degree 0, 1, or 2 is a linear forest.[4] [5] 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] [7] Any linear forest is a subgraph of the path graph with the same number of vertices.[8]

Extensions to the notation

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.

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]

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

\Delta

, the linear arboricity is always at least

\lceil\Delta/2\rceil

, and it is conjectured that it is always at most

\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

\Delta3/2

, and there exist graphs for which it is at least proportional to this quantity.[12]

Notes and References

  1. Harary . Frank . Frank Harary . September 1970 . Covering and Packing in Graphs, I . Annals of the New York Academy of Sciences . en . 175 . 1 . 198–205 . 10.1111/j.1749-6632.1970.tb56470.x . 0077-8923 . 1749-6632 . Wiley Online Library.
  2. Burr . Stefan A. . Stefan Burr . Roberts . John A. . May 1974 . On Ramsey numbers for linear forests . Discrete Mathematics . North-Holland Publishing Company . 8 . 3 . 245–250 . 10.1016/0012-365x(74)90136-8 . 0012-365X . 1872-681X . 335325 . Elsevier ScienceDirect.
  3. Brandstädt . Andreas . Andreas Brandstädt . Giakoumakis . Vassilis . Milanič . Martin . 2018-12-11 . Weighted efficient domination for some classes of H-free and of (H1,H2)-free graphs . Discrete Applied Mathematics . Elsevier B.V. . 250 . 130–144 . 10.1016/j.dam.2018.05.012 . 0166-218X . 3868662 . . free .
  4. Enomoto . Hikoe . Péroche . Bernard . Summer 1984 . The Linear Arboricity of Some Regular Graphs . Journal of Graph Theory . en . 8 . 2 . 309–324 . 10.1002/jgt.3190080211 . 0364-9024 . 1097-0118 . Wiley Online Library.
  5. Book: Jain . Sparsh . Algorithms and Discrete Applied Mathematics: 8th International Conference, CALDAM 2022 . Pallathumadam . Sreejith K. . Rajendraprasad . Deepak . February 10–12, 2022 . Springer Nature . 978-3-030-95017-0 . Balachandran . Niranjan . . 13179 . Puducherry, India . Cham, Switzerland . 103–114 . en . B0-VPG Representation of AT-free Outerplanar Graphs . 10.1007/978-3-030-95018-7_9 . Inkulu . R. . https://link.springer.com/chapter/10.1007/978-3-030-95018-7_9 . SpringerLink and Google Books.
  6. de Verdière . Yves Colin . Yves Colin de Verdière . October 1990 . Sur un Nouvel Invariant des Graphes et un Critère de Planarité . Journal of Combinatorial Theory, Series B . fr . Academic Press, Inc. . 50 . 1 . 11–21 . 10.1016/0095-8956(90)90093-F . 0095-8956 . Elsevier ScienceDirect.
  7. Book: van der Holst . Hein . Graph Theory and Combinatorial Biology . Lovász . László . László Lovász . Schrijver . Alexander . Alexander Schrijver . 1999 . János Bolyai Mathematical Society (Hungarian: Bolyai János Matematikai Társulat) . 963-8022-90-6 . Lovász . László . Bolyai Society Mathematical Studies . 7 . . 29–85 [1–43] . The Colin de Verdière graph parameter . 1217-4696 . 1673503 . . Associated with the "International Colloquium on Combinatorics and Graph Theory" in Balatonlelle on July 1996 (see p. 5 and http://wwwold.sztaki.hu/library/publtop/gyarf.jhtml). . Preliminary version, March 1997 . Gyárfás . András . Katona . Gyula . Recski . András . Székely . László . http://www.cs.elte.hu/~lovasz/colinsurv.ps . https://web.archive.org/web/20070206001555/http://www.cs.elte.hu/~lovasz/colinsurv.ps . 2007-02-06 . dead.
  8. Clark . Curtis . An Approach to Graph Achievement Games: Ultimately Economical Graphs . 1984 . PhD . University of Michigan . (UMI 8502782) . Ann Arbor, Michigan . 979-8-204-34535-5 . ProQuest Dissertations & Theses Global.
  9. Habib . M. . Peroche . B. . 1982 . Some problems about linear arboricity . Discrete Mathematics . North-Holland Publishing Company . 41 . 2 . 219–220 . 10.1016/0012-365x(82)90209-6 . 0012-365X . free .
  10. Faudree . Ralph J. . Ralph Faudree . Gould . Ronald J. . Ronald Gould (mathematician) . Jacobson . Michael S. . Michael Scott Jacobson . 28 March 2009 . Pancyclic graphs and linear forests . Discrete Mathematics . Elsevier B.V. . 309 . 5 . 1178–1189 . 10.1016/j.disc.2007.12.094 . 0012-365X . free .
  11. .
  12. .

This article is licensed under the GNU Free Documentation License. It uses material from the Wikipedia article "Linear forest".

Except where otherwise indicated, Everything.Explained.Today is © Copyright 2009-2024, A B Cryer, All Rights Reserved. Cookie policy.