Означает ли ширина дерева

Пусть $k$ фиксировано, и пусть $G$ (связный) граф. Если я не ошибаюсь, из работы Бодлендера [1, теорема 3.11] следует, что если ширина дерева $G$ примерно равна $2k^3$ , то $G$ содержит звезду $K_{1,k}$ в качестве минора.

Можем ли мы сделать срок $2k^3$ меньше? То есть, говорит ли ширина дерева, по крайней мере, $k$ уже подразумевает существование $K_{1,k}$ -минора? Есть ли где-нибудь доказательства?

[1] Bodlaender, HL (1993). На линейном времени второстепенные тесты с поиском по глубине. Журнал Алгоритмов, 14 (1), 1-23.

Действительно, каждый граф без K 1 , k минора имеет ширину дерева не более k - 1 . Мы докажем это ниже, сначала несколько определений:$G$$K_{1,k}$$k-1$

Пусть является древесная ширина из G и & omega ( G ) быть максимальный размер клики в G . Граф H является триангуляцией G, если G является подграфом H, а H хордовый (т. Е. Не имеет индуцированных циклов по крайней мере в 4 вершинах). Триангуляцией Н из G является минимальной триангуляции , если нет надлежащего подграф H не является также триангуляция G . Подмножество X вершин группы $tw(G)$$G$$\omega(G)$$G$$H$$G$$G$$H$$H$$4$$H$$G$$H$$G$$X$$G$$H$$G$$X$$H$H

Из приведенной выше формулы следует, что для доказательства того, что достаточно доказать, что все потенциальные максимальные клики в имеют размер не более . Теперь докажем это. Пусть - потенциальная максимальная клика группы , и пусть .G k X G | X | ≥ k + $tw(G) \leq k-1$$G$$k$$X$$G$$|X| \geq k+1$

Мы будем использовать следующую характеристику потенциальных максимальных клик: множество вершин является потенциальной максимальной кликой в если и только если для каждой пары , несмежных (различных) вершин в существует путь из в в со всеми его внутренними вершинами наружу из . Эту характеристику можно найти в статье Treewidth и Minimum Fill-in: группировка минимальных разделителей по Bouchitte и Todinca.G u v X P u , v u v G $X$$G$$u$$v$$X$$P_{u,v}$$u$$v$$G$$X$

С этой характеристикой легко вывести минор из . Пусть . Для каждой вершины , либо является ребром или существует путь из в со всеми внутренними вершинами вне . Для всех , несмежных с все внутренние вершины в . В итоге мы получаем минор в котором смежна со всем , и X u ∈ X v ∈ X ∖ { u } u v G P u , v u v X v ∈ X u P u , v u G u X | X | ≥ k + 1 u $K_{1,k}$$X$$u \in X$$v \in X \setminus \{u\}$$uv$$G$$P_{u,v}$$u$$v$$X$$v \in X$$u$$P_{u,v}$$u$$G$$u$$X$$|X| \geq k+1$ . Таким образом, степень в этом миноре составляет не менее , что завершает доказательство.$u$$k$