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