Linear forest

From Wikipedia, the free encyclopedia

In graph theory, a branch of mathematics, a linear forest is a kind of forest where each component is a path graph,[1]: 200  or a disjoint union of nontrivial paths.[2]: 246  Equivalently, it is an acyclic and claw-free graph.[3]: 130, 131  An acyclic graph where every vertex has degree 0, 1, or 2 is a linear forest.[4]: 310 [5]: 107  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]: 13, 19–21 [7]: 29, 35, 67 (3, 6, 29)  Any linear forest is a subgraph of the path graph with the same number of vertices.[8]: 55 

Extensions to the notation[edit]

According to Habib and Peroche, a k-linear forest consists of paths of k or fewer nodes each.[9]: 219 

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]: 245, 246 

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]: 1178, 1179 

Derived concepts[edit]

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]

References[edit]

  1. ^ Harary, Frank (September 1970). "Covering and Packing in Graphs, I". Annals of the New York Academy of Sciences. 175 (1): 198–205. doi:10.1111/j.1749-6632.1970.tb56470.x. eISSN 1749-6632. ISSN 0077-8923 – via Wiley Online Library.
  2. ^ a b 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. eISSN 1872-681X. ISSN 0012-365X. MR 0335325 – via Elsevier ScienceDirect.
  3. ^ Brandstädt, Andreas; 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. 250. Elsevier B.V.: 130–144. doi:10.1016/j.dam.2018.05.012. ISSN 0166-218X. MR 3868662. EBSCOhost 45704539, 132688071 – via Elsevier ScienceDirect.
  4. ^ Enomoto, Hikoe; Péroche, Bernard (Summer 1984). "The Linear Arboricity of Some Regular Graphs". Journal of Graph Theory. 8 (2): 309–324. doi:10.1002/jgt.3190080211. eISSN 1097-0118. ISSN 0364-9024 – via Wiley Online Library.
  5. ^ Jain, Sparsh; Pallathumadam, Sreejith K.; Rajendraprasad, Deepak (February 10–12, 2022). "B0-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 – via SpringerLink and Google Books.
  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. ISSN 0095-8956 – via Elsevier ScienceDirect.
  7. ^ van der Holst, Hein; Lovász, László; Schrijver, Alexander (1999) [Preliminary version, March 1997]. "The Colin de Verdière graph parameter". In Lovász, László; Gyárfás, András; Katona, Gyula; Recski, András; Székely, László (eds.). Graph Theory and Combinatorial Biology. Bolyai Society Mathematical Studies. Vol. 7. Budapest, Hungary: János Bolyai Mathematical Society (Hungarian: Bolyai János Matematikai Társulat). pp. 29-85 [1-43]. ISBN 963-8022-90-6. ISSN 1217-4696. MR 1673503. Archived from the original on 2007-02-06. 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). {{cite book}}: External link in |postscript= (help)CS1 maint: postscript (link)
  8. ^ Clark, Curtis (1984). An Approach to Graph Achievement Games: Ultimately Economical Graphs (PhD thesis). Ann Arbor, Michigan: University of Michigan. 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. ISSN 0012-365X – via Elsevier ScienceDirect.
  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. ISSN 0012-365X – via Elsevier ScienceDirect.
  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.
Retrieved from "https://en.wikipedia.org/w/index.php?title=Linear_forest&oldid=1224742671"