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.

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$.

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.

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.