Линейная древесность

Линейная древесность

Нерешённые проблемы математики

: Любой граф с максимальной степенью ${\displaystyle \Delta }$ имеет линейную древесность, не превосходящую ${\displaystyle \lceil (\Delta +1)/2\rceil }$?

Линейная древесность графа ${\displaystyle G}$ с максимальной степенью ${\displaystyle \Delta }$ всегда не меньше ${\displaystyle \lceil \Delta /2\rceil }$, поскольку каждый линейный лес может использовать только два из рёбер вершины максимальной степени. Гипотеза о линейной древесности Акиямы, Экзоо и Харари^[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].

В отличие от древесности, которая может быть установлена за

Для улучшения этой статьи желательно: Проверить качество перевода с иностранного языка. Исправить статью согласно стилистическим правилам Википедии. После исправления проблемы исключите её из списка. Удалите шаблон, если устранены все недостатки.