Linjär skog

Inom grafteorin , en gren av matematiken, är en linjär skog en sorts skog som bildas från den osammanhängande föreningen av väggrafer . Det är en oriktad graf utan cykler där varje vertex har grader som högst två. Linjära skogar är samma sak som klofria skogar. De är de grafer vars Colin de Verdière-grafinvariant är högst 1.

Den linjära arboriciteten för en graf är det minsta antalet linjära skogar som grafen kan delas in i. För en graf med maximal grad $\Delta$ , är den linjära arboriciteten alltid minst ${\displaystyle \lceil \Delta /2\rceil } ,$ och det antas att den alltid är högst $\lfloor (\Delta +1)/2\rfloor$ .

En linjär färgning av en graf är en korrekt graffärgning där den inducerade subgrafen som bildas av varje två färger är en linjär skog. Det linjära kromatiska talet för en graf är det minsta antalet färger som används av någon linjär färgning. Det linjära kromatiska talet är som mest proportionellt mot ${\displaystyle \Delta ^{3/2}} ,$ och det finns grafer för vilka det åtminstone är proportionellt mot denna kvantitet.