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 maximális fokszámú gráf esetén a lineáris arboricitás mindig legalább , és egy sejtés szerint legfeljebb .[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 -nel arányos, és néhány gráf esetében ez az alsó korlátra is igaz.[3]