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

10

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

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

Florent Foucaud
fonte
9
tw para gráficos de acordes. (G)=ω(G)1
Yixin Cao
como a largura da árvore é fechada sob subgráficos, se um gráfico tem K n como subgrafo, a largura da árvore de G deve ser pelo menos a largura da árvore de K n , que é n - 1 . GKnKnn1
Mateus de Oliveira Oliveira
11
@ 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
11
@ Bart Jansen: gráficos divididos são cordais.
Florent Foucaud
11
@FlorentFoucaud, considere transformar sua edição em uma resposta.
Vinicius dos Santos

Respostas:

10

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

GHtw(G)tw(H)ω(G)1

HH

[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
11
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
11
@Saeed Possivelmente, mas espero especialmente encontrar alguma discussão sobre o tópico nesse documento!
Florent Foucaud
6

Gtw(G)3ω(G)/22

Gtw(G)6ω(G)1G

[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