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

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

Нерозв'язана проблема математики:

Чи в будь-якого графа з найбільшим степенем

\Delta

лінійна деревність не перевищує

\lceil (\Delta +1)/2\rceil

?

(більше нерозв'язаних проблем математики)

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

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

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

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

Примітки

↑ Akiyama, Exoo, Harary, 1981.
↑ Akiyama, Exoo, Harary, 1981, с. 69–72.
↑ Ferber, Fox, Jain, 2018.
↑ Alon, Teague, Wormald, 2001, с. 11–16.
↑ Shermer, 1996, с. 234–239.
↑ 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.

[FOOTNOTEAkiyama,_Exoo,_Harary1981-1] Akiyama, Exoo, Harary, 1981.

[FOOTNOTEAkiyama,_Exoo,_Harary198169–72-2] Akiyama, Exoo, Harary, 1981, с. 69–72.

[FOOTNOTEFerber,_Fox,_Jain2018-3] Ferber, Fox, Jain, 2018.

[FOOTNOTEAlon,_Teague,_Wormald200111–16-4] Alon, Teague, Wormald, 2001, с. 11–16.

[FOOTNOTEShermer1996234–239-5] Shermer, 1996, с. 234–239.

[FOOTNOTEDuncan,_Eppstein,_Kobourov2004340–346-6] Duncan, Eppstein, Kobourov, 2004, с. 340–346.

[1]

[2]

[3]

[4]

[5]

[6]