Relação entre largura da árvore e número de clique

Existe alguma classe gráfica agradável para a qual a largura da árvore é delimitada por uma função do número de clique , ou seja, ? $tw(G)$ $\omega(G)$ $tw(G)\leq f(\omega(G))$

Por exemplo, é um fato clássico que, para qualquer gráfico acorde , temos . Portanto, classes relacionadas a gráficos de acordes podem ser boas candidatas. $G$ $tw(G)=\omega(G)-1$

graph-theory treewidth Florent Foucaud
fonte

para gráficos de acordes.

(G) = ω (G) - 1

$(G) = \omega(G) - 1$

Yixin Cao

como a largura da árvore é fechada sob subgráficos, se um gráfico

tem

como subgrafo, a largura da árvore de G deve ser pelo menos a largura da árvore de

, que é

G

$G$

K_{n}

$K_n$

K_{n}

$K_n$

n - 1

$n-1$

Mateus de Oliveira Oliveira

@ Matheus Eu acho que a questão é o contrário. Ele está pedindo um limite superior e seu exemplo fornece um limite inferior.

Vinicius dos Santos

@ Bart Jansen: gráficos divididos são cordais.

Florent Foucaud

@FlorentFoucaud, considere transformar sua edição em uma resposta.

Vinicius dos Santos

Respostas:

Em desta página um teorema é mencionado que fornece essas classes:

$G$ $H$ $tw(G)\leq tw(H)\omega(G)-1$

$H$ $H$

[1] P. Scheffler, Quais gráficos delimitaram a largura das árvores? Rostocker Math. Kolloq. 41 (1990) 31-38.

Florent Foucaud
fonte

"inacessível"? você quer dizer que o papel não está online?

vzn

Na verdade, a princípio, pensei que fosse uma palestra em conferência, mas obviamente isso tem alguns números de página. Existe um site para a revista ( math.uni-rostock.de/math/pub/romako ), perguntei se é possível obter uma cópia.

Florent Foucaud

Eu acho que também não é difícil provar você mesmo. Possivelmente é mais rápido do que receber uma cópia de papel :)

Saeed

@Saeed Possivelmente, mas espero especialmente encontrar alguma discussão sobre o tópico nesse documento!

Florent Foucaud

$G$ $tw(G)\leq 3\omega(G)/2-2$

$G$ $tw(G)\leq 6\omega(G)-1$ $G$

[1] K. Cameron, S. Chaplick, CT Hoang. Sobre a estrutura de gráficos sem pan (pan, even hole), 2015. https://arxiv.org/abs/1508.03062

[2] K. Cameron, MVG da Silva, S. Huang, K. Vušković. Estrutura e algoritmos para gráficos sem limite (cap, even hole), 2016. https://arxiv.org/abs/1611.08066

Florent Foucaud
fonte