# Linear forest > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Linear_forest > Markdown URL: https://mediated.wiki/source/Linear_forest.md > Source: https://en.wikipedia.org/wiki/Linear_forest > Source revision: 1336670961 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) {{Short description|Graph formed from disjoint paths}} {{CS1 config|mode=cs2}} thumb|upright=0.9|A linear forest In [graph theory](/source/graph_theory), a branch of [mathematics](/source/mathematics), a '''linear forest''' is a kind of [forest](/source/forest_(graph_theory)) where each [component](/source/component_(graph_theory)) is a [path graph](/source/path_graph),{{citation |last=Harary |first=Frank |author-link=Frank Harary |date=September 1970 |title=Covering and Packing in Graphs, I |journal=Annals of the New York Academy of Sciences |volume=175 |issue=1 |pages=198–205 |doi=10.1111/j.1749-6632.1970.tb56470.x |bibcode=1970NYASA.175..198H }} or a [disjoint union](/source/Disjoint_union_of_graphs) of nontrivial paths.{{citation |last1=Burr |first1=Stefan A. |author-link=Stefan Burr |last2=Roberts |first2=John A. |date=May 1974 |title=On Ramsey numbers for linear forests |journal=Discrete Mathematics |publisher=North-Holland Publishing Company |volume=8 |issue=3 |pages=245–250 |doi=10.1016/0012-365x(74)90136-8 |mr=335325}} Equivalently, it is an [acyclic](/source/cycle_(graph_theory)) and [claw-free](/source/claw-free_graph) [graph](/source/graph_(discrete_mathematics)).{{citation |last1=Brandstädt |first1=Andreas |author-link=Andreas Brandstädt |last2=Giakoumakis |first2=Vassilis |last3=Milanič |first3=Martin |date=2018 |title=Weighted efficient domination for some classes of H-free and of (H1,H2)-free graphs |journal=Discrete Applied Mathematics |publisher=[Elsevier](/source/Elsevier) B.V. |volume=250 |pages=130–144 |doi=10.1016/j.dam.2018.05.012 |mr=3868662 |id={{EBSCOhost|45704539|132688071}} |doi-access=free }} An acyclic graph where every [vertex](/source/vertex_(graph_theory)) has [degree](/source/degree_(graph_theory)) 0, 1, or 2 is a linear forest.{{citation |last1=Enomoto |first1=Hikoe |last2=Péroche |first2=Bernard |date= 1984 |title=The Linear Arboricity of Some Regular Graphs |journal=Journal of Graph Theory |volume=8 |issue=2 |pages=309–324 |doi=10.1002/jgt.3190080211 }}{{citation |last1=Jain |first1=Sparsh |chapter-url=https://books.google.com/books?id=ZKJaEAAAQBAJ&dq=%22linear+forest%22+degree&pg=PA107 |title=Algorithms and Discrete Applied Mathematics: 8th International Conference, CALDAM 2022 |last2=Pallathumadam |first2=Sreejith K. |last3=Rajendraprasad |first3=Deepak |date=February 10–12, 2022 |publisher=Springer Nature |isbn=978-3-030-95017-0 |editor-last=Balachandran |editor-first=Niranjan |series=[Lecture Notes in Computer Science](/source/Lecture_Notes_in_Computer_Science) |volume=13179 |location=Puducherry, India |publication-place=Cham, Switzerland |pages=103–114 |language=en |chapter=B0-VPG Representation of AT-free Outerplanar Graphs |doi=10.1007/978-3-030-95018-7_9 |editor-last2=Inkulu |editor-first2=R. |arxiv=2209.08269 }} An [undirected graph](/source/undirected_graph) has [Colin de Verdière graph invariant](/source/Colin_de_Verdi%C3%A8re_graph_invariant) at most 1 [if and only if](/source/if_and_only_if) it is a (node-)disjoint union of paths, i.e. it is linear.{{citation |last=de Verdière |first=Yves Colin |author-link=Yves Colin de Verdière |date=October 1990 |title=Sur un Nouvel Invariant des Graphes et un Critère de Planarité |journal=Journal of Combinatorial Theory, Series B |language=fr |publisher=Academic Press, Inc. |volume=50 |issue=1 |pages=11–21 |doi=10.1016/0095-8956(90)90093-F }}{{citation |last1=van der Holst |first1=Hein |title=Graph Theory and Combinatorial Biology |last2=Lovász |first2=László |author-link2=László Lovász |last3=Schrijver |first3=Alexander |author-link3=Alexander Schrijver |date=1999 |publisher=[János Bolyai Mathematical Society](/source/J%C3%A1nos_Bolyai_Mathematical_Society) |isbn=963-8022-90-6 |editor-last=Lovász |editor-first=László |series=Bolyai Society Mathematical Studies |volume=7 |publication-place=[Budapest, Hungary](/source/Budapest%2C_Hungary) |pages=29–85 |chapter=The Colin de Verdière graph parameter |mr=1673503 }}. [https://web.archive.org/web/20070206001555/http://www.cs.elte.hu/~lovasz/colinsurv.ps Preliminary version], March 1997; see pp. 29, 35, 67 (pp. 3, 6, 29 of preliminary version) Any linear forest is a subgraph of the path graph with the same number of vertices.{{citation |last=Clark |first=Curtis |title=An Approach to Graph Achievement Games: Ultimately Economical Graphs |date=1984 |type=PhD thesis |publisher=University of Michigan |id={{ProQuest|303324911}} (UMI 8502782) |place=Ann Arbor, Michigan |isbn=979-8-204-34535-5 |via=ProQuest Dissertations & Theses Global|page=55}} == Extensions to the notation == According to Habib and Peroche, a ''k''-linear forest consists of paths of ''k'' or fewer nodes each.{{citation |last1=Habib |first1=M. |last2=Peroche |first2=B. |date=1982 |title=Some problems about linear arboricity |journal=Discrete Mathematics |publisher=North-Holland Publishing Company |volume=41 |issue=2 |pages=219–220 |doi=10.1016/0012-365x(82)90209-6 |doi-access=free }} According to Burr and Roberts, an (''n'', ''j'')-linear forest has ''n'' vertices and ''j'' of its component paths have an [odd](/source/parity_(mathematics)) number of vertices. According to Faudree et al., a (''k'', ''t'')-linear or (''k'', ''t'', ''s'')-linear forest has ''k'' [edge](/source/edge_(graph_theory))s, and ''t'' components of which ''s'' are single vertices; ''s'' is omitted if its value is not critical.{{citation |last1=Faudree |first1=Ralph J. |author-link=Ralph Faudree |last2=Gould |first2=Ronald J. |author-link2=Ronald Gould (mathematician) |last3=Jacobson |first3=Michael S. |author-link3=Michael Scott Jacobson |date=28 March 2009 |title=Pancyclic graphs and linear forests |journal=Discrete Mathematics |publisher=Elsevier B.V. |volume=309 |issue=5 |pages=1178–1189 |doi=10.1016/j.disc.2007.12.094 |doi-access=free }} == Derived concepts == The [linear arboricity](/source/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 [conjecture](/source/conjecture)d that it is always at most \lfloor(\Delta+1)/2\rfloor.{{citation | last = Alon | first = N. | authorlink = Noga Alon | doi = 10.1007/BF02783300 | doi-access = free | issue = 3 | journal = [Israel Journal of Mathematics](/source/Israel_Journal_of_Mathematics) | mr = 955135 | pages = 311–325 | title = The linear arboricity of graphs | volume = 62 | year = 1988| citeseerx = 10.1.1.163.1965 }}. A linear coloring of a graph is a proper [graph coloring](/source/graph_coloring) in which the [induced subgraph](/source/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 \Delta^{3/2}, and there exist graphs for which it is at least proportional to this quantity.{{citation | last = Yuster | first = Raphael | author-link = Raphael Yuster | doi = 10.1016/S0012-365X(97)00209-4 | issue = 1–3 | journal = [Discrete Mathematics](/source/Discrete_Mathematics_(journal)) | mr = 1614290 | pages = 293–297 | title = Linear coloring of graphs | volume = 185 | year = 1998| doi-access = free }}. ==References== {{reflist}} Category:Trees (graph theory) Category:Graph families --- Adapted from the Wikipedia article [Linear forest](https://en.wikipedia.org/wiki/Linear_forest) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Linear_forest?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.