Equivalência entre duas definições de largura da árvore

Largura da árvore :

1) Por gráficos de acordes : tamanho da maior camarilha$(\omega (G))$- 1 em uma conclusão cordial do gráfico$G$.

2) Por decomposição de árvores :

Uma decomposição de árvores de $G = (V , E)$ consiste em uma árvore $T$ (em um conjunto de nós diferente de $G$) e um subconjunto $V_t ⊆ V$ associado a cada nó $t$ do $T$. (Vamos chamar esses subconjuntos$V_t$ as “peças” da decomposição da árvore.) Às vezes, escreveremos isso como o par ordenado $(T , {V_t : t ∈ T })$. A árvore T e a coleção de peças$\{V_t : t ∈ T \}$ deve satisfazer as três propriedades a seguir

(Cobertura do nó) Todos os nós do$G$ pertence a pelo menos uma peça $V_t$.

(Cobertura da borda) Para cada borda$e$ do $G$, tem alguma peça $V_t$ contendo ambas as extremidades de $e$.

(Coerência) Vamos$t_1, t_2,$ e $t_3$ ser três nós de $T$ de tal modo que $t_2$ encontra-se no caminho de $t_1$ para $t_3$. Então, se um nó$v$ do $G$ pertence a ambos $V_{t_{1}}$ e $V_{t_{3}}$, também pertence a $V_{t_2}$

Então, definimos a largura de uma decomposição de árvore $(T , {V_t })$ ser um a menos do que o tamanho máximo de qualquer peça $V_t$ (No geral $t$):

Reivindicação 1: Se o tamanho da maior camarilha em uma decomposição acorde do gráfico for $k$ então, por decomposição da árvore, obteremos a largura da árvore $k$

Prova: vamos supor que o maior tamanho de clique no gráfico de conclusão de acordes seja$k$, existe um saco (subconjunto de vértices do gráfico) que contém a clique (devido à cobertura da borda). então terminamos.

reivindicação 2 : se a largura da árvore for$k$ pelo método de decomposição de árvores, em seguida, pelo método de conclusão de acordes também é $k$

Pergunta: Como provar a reivindicação 2. Serão bem-vindas as provas de alto nível.

Primeiro, deixe-me observar que a afirmação, conforme declarada na pergunta, é falsa: Considere o seguinte gráfico:

$\begin{matrix} & & 2& - & 3\\ & \diagup\\ 1 & & | & & |\\ & \diagdown \\ & &4 &-& 5 \end{matrix}$

O gráfico completo $5$vértices é uma conclusão cordial deste gráfico. No entanto, este gráfico possui uma largura de árvore$2$. (Uma decomposição é$\{1,2,4\}$, $\{2,3,4\}$, $\{3,4,5\}$ )

A reivindicação correta é

A largura da árvore $G$ de é o tamanho da maior camarilha $\omega(G) - 1$em uma conclusão de acordes com o maior clique mínimo do gráfico$G$.

Agora, uma prova é a seguinte: se a largura da árvore de $G$ por decomposição de árvores é $k$, então toda decomposição de árvore tem um saco de tamanho pelo menos $k$. Utilizamos o conceito de um gráfico separador de um artigo de Parra e Scheffler , em particular o fato de que cada clique máximo no gráfico separador de$G$ é uma decomposição de árvores de $G$ (Isso pode ser visto comparando a definição de decomposição de árvores com as do artigo)

Então, pelo Teorema 4.7$^*$ do mesmo artigo, cada conclusão mínima de acordes $G$tem todos os sacos de decomposição de uma árvore como um clique. Isso significa que cada conclusão mínima de acordes$G$ tem uma panelinha de tamanho $k$, portanto, o método de conclusão de acordes também fornece uma largura de árvore de $k$. $\square$

*: Parafraseado em nossa notação, o Teorema 4.7 declara:

Um gráfico $H$ é uma conclusão cordial mínima de $G$ se e apenas se $H$ é o gráfico $G$ com exatamente as arestas adicionadas, de modo que todos os vértices sejam $\mathcal{S}$são panelinhas. Aqui$\mathcal{S}$ é um clique máximo no gráfico separador, que consiste em separadores mínimos de $G$.

Tentei encontrar uma prova usando apenas técnicas elementares, mas não acho que seria fácil encontrar uma prova fácil sem uma teoria mais profunda.