„Lineáris erdő” változatai közötti eltérés
Syp (vitalap | szerkesztései) Új oldal, tartalma: „A matematika, azon belül a gráfelmélet területén '''lineáris erdő''' ''(linear forest)'' alatt olyan erdő értendő, amit ú…” |
(Nincs különbség)
|
A lap 2018. március 27., 13:12-kori változata
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]
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>.
- ↑ 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.