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

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

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

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

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

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

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

Література

• Jin Akiyama, Geoffrey Exoo, Frank Harary. Covering and packing in graphs. IV. Linear arboricity // Networks. — 1981. — Т. 11, вип. 1. — С. 69–72. — DOI:10.1002/net.3230110108.
• Asaf Ferber, Jacob Fox, Vishesh Jain. Towards the linear arboricity conjecture. — 2018. — arXiv:1809.04716.
• Noga Alon, Teague V. J., Wormald N. C. Linear arboricity and linear k-arboricity of regular graphs // Graphs and Combinatorics. — 2001. — Т. 17, вип. 1. — С. 11–16. — DOI:10.1007/PL00007233.
• Thomas C. Shermer. On rectangle visibility graphs. III. External visibility and complexity // Proceedings of the 8th Canadian Conference on Computational Geometry (CCCG'96). — 1996. — С. 234–239.
• Christian A. Duncan, David Eppstein, Stephen G. Kobourov. The geometric thickness of low degree graphs // Proc. 20th ACM Symposium on Computational Geometry (SoCG 2004). — 2004. — С. 340–346. — DOI:10.1145/997817.997868.