Hay varias clases interesantes de gráficos con ancho de árbol acotado. Por ejemplo, árboles (ancho de árbol 1), gráficos paralelos en serie (ancho de árbol 2), gráficos de plano externo (ancho de árbol 2), gráficos -outerplanar (ancho de árbol O (k)), gráficos de ancho de rama k (ancho de árbol O (k)), .. .
Pregunta: ¿Hay ejemplos de clases interesantes de gráficos cuyo ancho de árbol no esté limitado por una constante, sino por una función de bajo crecimiento?
- ¿Existen clases de gráficos bien conocidas con el ancho de árbol ?
- ¿Hay clases bien conocidas de gráficos con el ancho de árbol ?
También estaría interesado en clases de gráficos con treewidth o O ( log log . . . N ) donde el logaritmo se repite un número constante de veces.
Obs: Por supuesto, es fácil cocinar familias artificiales de gráficos con un ancho de árbol dado, como la familia derejillas Así que estoy buscando principalmente una familia de gráficos que se hayan estudiado en otras ramas de la teoría de gráficos y que tengan un ancho de árbol u O ( log log n ) , pero un ancho de árbol no constante.
fuente
Respuestas:
fuente