Лінійна деревність

Ліні́йна дере́вність неорієнтованого графа — це найменша кількість лінійних лісів, на які можна розбити граф. Тут лінійний ліс — це ациклічний граф із найбільшим степенем два, тобто диз'юнктне об'єднання шляхів.

Нерозв'язана проблема математики: Чи в будь-якого графа з найбільшим степенем ${\displaystyle \Delta }$ лінійна деревність не перевищує ${\displaystyle \lceil (\Delta +1)/2\rceil }$? (більше нерозв'язаних проблем математики)

Лінійна деревність графа ${\displaystyle G}$ з найбільшим степенем ${\displaystyle \Delta }$ завжди не менша від ${\displaystyle \lceil \Delta /2\rceil }$, оскільки кожен лінійний ліс може використовувати лише два з ребер вершини найбільшого степеня. Гіпотеза про лінійну деревність Акіями^[en], Екзоо та Харарі^[1] стверджує, що ця нижня межа точна. За цією гіпотезою будь-який граф має лінійну деревність, яка не перевищує ${\displaystyle \lceil (\Delta +1)/2\rceil }$^[2]. Однак гіпотеза залишається недоведеною, і краща доведена верхня грань лінійної деревності дещо вища, ${\displaystyle \Delta /2+O(\Delta ^{2/3-c})}$ з деякою сталою ${\displaystyle c>0}$ (за Фербером, Фоксом і Джейном^[3]).

У регулярному графі лінійна деревність не може дорівнювати ${\displaystyle \Delta /2}$ оскільки кінцеві точки будь-якого шляху в одному з лінійних лісів не можуть мати двох суміжних вершин, використаних у цьому лісі. Тому, для регулярних графів, з гіпотези про лінійну деревність випливає, що лінійна деревність точно дорівнює ${\displaystyle \lceil (\Delta +1)/2\rceil }$.

Лінійна деревність є варіацією деревності графа, найменшої кількості лісів, на які можна розбити ребра графа. Досліджувалась також лінійна k-деревність, варіант лінійної деревності, в якій будь-який шлях у лінійному лісі може мати не більше k ребер^[4].

На відміну від деревності, яку можна встановити за поліноміальний час, задача встановлення лінійної деревності NP-складна. Навіть розпізнавання графів з лінійною деревністю два є NP-повною задачею^[5]. Однак для кубічних графів та інших графів з найбільшим степенем три лінійна деревність завжди дорівнює двом, а розклад на два лінійні ліси можна знайти за лінійний час за допомогою алгоритму, заснованого на пошуку в глибину^[6].