Relación entre ancho de árbol y número de camarilla

¿Hay algunas clases gráficas agradables para las cuales el ancho del árbol esté limitado por una función del número de camarilla , es decir, ? $tw(G)$ $\omega(G)$ $tw(G)\leq f(\omega(G))$

Por ejemplo, es un hecho clásico que para cualquier gráfico cordal , tenemos . Por lo tanto, las clases relacionadas con gráficos cordales podrían ser buenos candidatos. $G$ $tw(G)=\omega(G)-1$

graph-theory treewidth Florent Foucaud
fuente

para gráficos cordales.

(G) = ω (G) - 1

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

Yixin Cao

dado que el ancho de árbol se cierra al tomar subgráficos, si un gráfico

tiene

como subgráfico, entonces el ancho de árbol de G debe ser al menos el ancho de árbol de

, que es

G

$G$

K_{n}

$K_n$

K_{n}

$K_n$

n - 1

$n-1$

Mateus de Oliveira Oliveira

@Matheus Creo que la pregunta es al revés. Él está pidiendo un límite superior y su ejemplo le da un límite inferior.

Vinicius dos Santos

@Bart Jansen: los gráficos divididos son cordales.

Florent Foucaud

@FlorentFoucaud, deberías considerar convertir tu edición en una respuesta.

Vinicius dos Santos

Respuestas:

En esta página se menciona un teorema que proporciona tales clases:

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

$H$ $H$

[1] P. Scheffler, ¿Qué gráficos tienen un ancho de árbol acotado? Rostocker Math. Kolloq. 41 (1990) 31-38.

Florent Foucaud
fuente

"inaccesible"? ¿Quieres decir que el papel no está en línea?

vzn

En realidad, al principio pensé que se trataba de una conferencia, pero obviamente tiene algunos números de página. Hay un sitio web para la revista ( math.uni-rostock.de/math/pub/romako ), he preguntado si es posible obtener una copia.

Florent Foucaud

Creo que tampoco es difícil demostrarlo usted mismo. Posiblemente sea más rápido que recibir una copia de papel :)

Saeed

@Saeed Posiblemente, ¡pero especialmente espero encontrar alguna discusión sobre el tema en ese 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 la estructura de gráficas libres de (pan, even hole), 2015. https://arxiv.org/abs/1508.03062

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

Florent Foucaud
fuente