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