Lineáris erdő

A matematika, azon belül a gráfelmélet területén lineáris erdő (linear forest) alatt olyan erdő értendő, amit útgráfok diszjunkt uniója alkot. Ez egy olyan, körmentes irányítatlan gráf, melyben a csúcsok fokszáma legfeljebb kettő lehet. A lineáris erdők megegyeznek a karommentes erdőkkel, illetve azokkal a gráfokkal, melyek Colin de Verdière-gráfinvariánsa legfeljebb 1.^[1]

Egy gráf lineáris arboricitása azon lineáris erdők minimális száma, melyekbe a gráf élei felbonthatók. Egy $\Delta$ maximális fokszámú gráf esetén a lineáris arboricitás mindig legalább $\lceil \Delta /2\rceil$ , és egy sejtés szerint legfeljebb $\lfloor (\Delta +1)/2\rfloor$ .^[2]

Egy gráf lineáris színezése olyan jó csúcsszínezés, melyben bármely két szín által feszített részgráf lineáris erdő. Egy gráf lineáris kromatikus száma a lineáris színezéskor felhasznált legkevesebb lehetséges szín száma. A lineáris kromatikus szám felső korlátja $\Delta ^{3/2}$ -nel arányos, és néhány gráf esetében ez az alsó korlátra is igaz.^[3]

Fordítás

Ez a szócikk részben vagy egészben a Linear forest című angol Wikipédia-szócikk ezen változatának fordításán alapul. Az eredeti cikk szerkesztőit annak laptörténete sorolja fel. Ez a jelzés csupán a megfogalmazás eredetét és a szerzői jogokat jelzi, nem szolgál a cikkben szereplő információk forrásmegjelöléseként.

Jegyzetek

↑ van der Holst, Hein; Lovász, László & Schrijver, Alexander (1999), "The Colin de Verdière graph parameter", Graph Theory and Combinatorial Biology (Balatonlelle, 1996), vol. 7, Bolyai Soc. Math. Stud., Budapest: János Bolyai Math. Soc., pp. 29–85, <http://www.cs.elte.hu/~lovasz/colinsurv.ps> Archiválva 2016. március 3-i dátummal a Wayback Machine-ben Archivált másolat. [2016. március 3-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. március 27.).
↑ Alon, N. (1988), "The linear arboricity of graphs", Israel Journal of Mathematics 62 (3): 311–325, DOI 10.1007/BF02783300.
↑ Yuster, Raphael (1998), "Linear coloring of graphs", Discrete Mathematics 185 (1-3): 293–297, DOI 10.1016/S0012-365X(97)00209-4.

[1] van der Holst, Hein; Lovász, László & Schrijver, Alexander (1999), "The Colin de Verdière graph parameter", Graph Theory and Combinatorial Biology (Balatonlelle, 1996), vol. 7, Bolyai Soc. Math. Stud., Budapest: János Bolyai Math. Soc., pp. 29–85, <http://www.cs.elte.hu/~lovasz/colinsurv.ps> Archiválva 2016. március 3-i dátummal a Wayback Machine-ben Archivált másolat. [2016. március 3-i dátummal az eredetiből archiválva]. (Hozzáférés: 2018. március 27.).

[2] Alon, N. (1988), "The linear arboricity of graphs", Israel Journal of Mathematics 62 (3): 311–325, DOI 10.1007/BF02783300.

[3] Yuster, Raphael (1998), "Linear coloring of graphs", Discrete Mathematics 185 (1-3): 293–297, DOI 10.1016/S0012-365X(97)00209-4.

[1]

[2]

[3]