Лінійна деревність
Ліні́йна дере́вність неорієнтованого графа — це найменша кількість лінійних лісів, на які можна розбити граф. Тут лінійний ліс — це ациклічний граф із найбільшим степенем два, тобто диз'юнктне об'єднання шляхів.
Лінійна деревність графа з найбільшим степенем завжди не менша від , оскільки кожен лінійний ліс може використовувати лише два з ребер вершини найбільшого степеня. Гіпотеза про лінійну деревність Шаблон:Нп, Екзоо та ХараріШаблон:Sfn стверджує, що ця нижня межа точна. За цією гіпотезою будь-який граф має лінійну деревність, яка не перевищує Шаблон:Sfn. Однак гіпотеза залишається недоведеною, і краща доведена верхня грань лінійної деревності дещо вища, з деякою сталою (за Фербером, Фоксом і ДжейномШаблон:Sfn).
У регулярному графі лінійна деревність не може дорівнювати оскільки кінцеві точки будь-якого шляху в одному з лінійних лісів не можуть мати двох суміжних вершин, використаних у цьому лісі. Тому, для регулярних графів, з гіпотези про лінійну деревність випливає, що лінійна деревність точно дорівнює .
Лінійна деревність є варіацією деревності графа, найменшої кількості лісів, на які можна розбити ребра графа. Досліджувалась також лінійна Шаблон:Mvar-деревність, варіант лінійної деревності, в якій будь-який шлях у лінійному лісі може мати не більше Шаблон:Mvar реберШаблон:Sfn.
На відміну від деревності, яку можна встановити за поліноміальний час, задача встановлення лінійної деревності NP-складна. Навіть розпізнавання графів з лінійною деревністю два є NP-повною задачеюШаблон:Sfn. Однак для кубічних графів та інших графів з найбільшим степенем три лінійна деревність завжди дорівнює двом, а розклад на два лінійні ліси можна знайти за лінійний час за допомогою алгоритму, заснованого на пошуку в глибинуШаблон:Sfn.