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

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

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

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

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

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

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

Примітки

1. Akiyama, Exoo, Harary, 1981.
2. Akiyama, Exoo, Harary, 1981, с. 69–72.
3. Ferber, Fox, Jain, 2018.
4. Alon, Teague, Wormald, 2001, с. 11–16.
5. Shermer, 1996, с. 234–239.
6. Duncan, Eppstein, Kobourov, 2004, с. 340–346.

Література

• 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.