Линейный лес

Линейный лес — это вид леса, образованного из дизъюнктного объединения путей. Это ориентированный граф, не имеющий циклов, в котором каждая вершина имеет степень, не превосходящую трёх. Линейные леса — это то же самое, что и леса без клешенй. Это также графы, инвариант Колен де Вердьера которых не превосходит 1.

Линейная древесность графа — это минимальное число линейных лесов, на которые граф может быть разложен. Для графа максимальной степени $\mathrm{\Delta <!--\; \Delta \; -->}$$\Delta$ линейная древесность всегда не менее $\lceil <!--\; \lceil \; -->\mathrm{\Delta <!--\; \Delta \; -->}/2\rceil <!--\; \rceil \; -->$$\lceil \Delta /2\rceil$, и есть гипотеза, что она всегда не превосходит $\lfloor <!--\; \lfloor \; -->(\mathrm{\Delta <!--\; \Delta \; -->}+1)/2\rfloor <!--\; \rfloor \; -->$$\lfloor (\Delta +1)/2\rfloor$.

Линейная раскраска графа — это собственная раскраска графов, в которой порождённый подграф, образованный любыми двумя цветами, образует линейный лес. Линейное хроматическое число графа — это наименьшее число цветов, используемых для любой линейной раскраски. Линейное хроматическое число как максимум пропорционально ${\mathrm{\Delta <!--\; \Delta \; -->}}^{3/2}$$\Delta ^{3/2}$ (где $\mathrm{\Delta <!--\; \Delta \; -->}$$\Delta$ — максимальная степень графа) и есть графы, для которых оно по меньшей мере пропорционально этой величине.