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

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 ${\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]

References

1. Harary, Frank (September 1970), "Covering and Packing in Graphs, I", Annals of the New York Academy of Sciences, 175 (1): 198–205, Bibcode:1970NYASA.175..198H, doi:10.1111/j.1749-6632.1970.tb56470.x
2. Burr, Stefan A.; Roberts, John A. (May 1974), "On Ramsey numbers for linear forests", Discrete Mathematics, 8 (3), North-Holland Publishing Company: 245–250, doi:10.1016/0012-365x(74)90136-8, MR   0335325
3. Brandstädt, Andreas; Giakoumakis, Vassilis; Milanič, Martin (2018), "Weighted efficient domination for some classes of H-free and of (H1,H2)-free graphs", Discrete Applied Mathematics, 250, Elsevier B.V.: 130–144, doi: 10.1016/j.dam.2018.05.012 , MR   3868662, EBSCOhost   45704539, 132688071
4. Enomoto, Hikoe; Péroche, Bernard (1984), "The Linear Arboricity of Some Regular Graphs", Journal of Graph Theory, 8 (2): 309–324, doi:10.1002/jgt.3190080211
5. Jain, Sparsh; Pallathumadam, Sreejith K.; Rajendraprasad, Deepak (February 10–12, 2022), "B₀-VPG Representation of AT-free Outerplanar Graphs", written at Puducherry, India, in Balachandran, Niranjan; Inkulu, R. (eds.), Algorithms and Discrete Applied Mathematics: 8th International Conference, CALDAM 2022, Lecture Notes in Computer Science, vol. 13179, Cham, Switzerland: Springer Nature, pp. 103–114, doi:10.1007/978-3-030-95018-7_9, ISBN   978-3-030-95017-0
6. de Verdière, Yves Colin (October 1990), "Sur un Nouvel Invariant des Graphes et un Critère de Planarité", Journal of Combinatorial Theory, Series B (in French), 50 (1), Academic Press, Inc.: 11–21, doi:10.1016/0095-8956(90)90093-F
7. van der Holst, Hein; Lovász, László; Schrijver, Alexander (1999), "The Colin de Verdière graph parameter", in Lovász, László (ed.), Graph Theory and Combinatorial Biology, Bolyai Society Mathematical Studies, vol. 7, Budapest, Hungary: János Bolyai Mathematical Society, pp. 29–85, ISBN   963-8022-90-6, MR   1673503 . Preliminary version, March 1997; see pp. 29, 35, 67 (pp. 3, 6, 29 of preliminary version)
8. Clark, Curtis (1984), An Approach to Graph Achievement Games: Ultimately Economical Graphs (PhD thesis), Ann Arbor, Michigan: University of Michigan, p. 55, ISBN   979-8-204-34535-5, ProQuest   303324911 (UMI 8502782) – via ProQuest Dissertations & Theses Global
9. Habib, M.; Peroche, B. (1982), "Some problems about linear arboricity", Discrete Mathematics, 41 (2), North-Holland Publishing Company: 219–220, doi: 10.1016/0012-365x(82)90209-6
10. Faudree, Ralph J.; Gould, Ronald J.; Jacobson, Michael S. (28 March 2009), "Pancyclic graphs and linear forests", Discrete Mathematics, 309 (5), Elsevier B.V.: 1178–1189, doi: 10.1016/j.disc.2007.12.094
11. Alon, N. (1988), "The linear arboricity of graphs", Israel Journal of Mathematics , 62 (3): 311–325, CiteSeerX   10.1.1.163.1965 , doi: 10.1007/BF02783300 , MR   0955135 .
12. Yuster, Raphael (1998), "Linear coloring of graphs", Discrete Mathematics , 185 (1–3): 293–297, doi: 10.1016/S0012-365X(97)00209-4 , MR   1614290 .