Линейный лес

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

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

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