Propiedad de ancho de árbol de algo

Vamos ser un parámetro gráfico (ex. De diámetro, número de dominación, etc)$s$

Una familia de gráficos tiene la propiedad s -treewidth si hay una función f tal que para cualquier gráfico G ∈ F , el ancho de árbol de G es como máximo f ( s ) .$\mathcal{F}$$s$$f$$G\in \mathcal{F}$$G$$f(s)$

Por ejemplo, supongamos que , y F sea ​​la familia de los gráficos planos. Entonces se sabe que cualquier gráfico plano de diámetro como máximo s tiene un ancho de árbol en la mayoría de las O ( s ) . En términos más generales, Eppstein demostró que una familia de gráficos tiene la propiedad diámetro-ancho de árbol si y solo si excluye algún gráfico de vértice como menor. Ejemplos de tales familias son gráficos de género constante, etc.$s = \mathit{diameter}$$\mathcal{F}$$s$$O(s)$

Como otro ejemplo, supongamos que . Fomin y Thilikos han demostrado un resultado análogo al de Eppstein al mostrar que una familia de gráficos tiene la propiedad domination-number-treewidth si y solo si F tiene un ancho de árbol local. Tenga en cuenta que esto sucede si y solo si F tiene la propiedad diámetro-árbol-ancho.$s = \mathit{domination{-}number}$$\mathcal{F}$$\mathcal{F}$

Preguntas:

1. ¿Para qué parámetros de gráfico es conocida la propiedad s -treewidth en gráficos planos?$s$$s$
2. $s$$s$
3. $s$$s$

Tengo la sensación de que estas preguntas tienen alguna relación con la teoría de la bidimensionalidad . Dentro de esta teoría, hay varios parámetros importantes. Por ejemplo, los tamaños del conjunto de vértices de retroalimentación, cubierta de vértice, coincidencia máxima mínima, cubierta de cara, conjunto dominante, conjunto dominante de borde, conjunto dominante de R, conjunto dominante conectado, conjunto dominante de borde conectado, conjunto dominante dominante de R, etc.

4. $s$$s$

$1$$s(G)$$s(G) \geq s(H)$$H$$G$$s$

$c$$s$$t$$t$$ct^2$

$s$$t$$t$$t$

• está cerrado bajo menores
• es arbitrariamente grande en t veces t rejillas para t suficientemente grande

Entonces s tiene la propiedad s-treeewidth. Consulte el reciente libro de complejidad parametrizada ( http://parameterized-algorithms.mimuw.edu.pl ) en el capítulo de ancho de árbol para obtener más información.

Entre su lista, (al menos) número de cubierta de vértice y tamaño de conjunto de vértice de retroalimentación, para gráficos en general.

1. $s$$\dots$

2. $s$$\dots$