¿El ancho de árbol

Dejemos que $k$ sea ​​fijo, y que $G$ sea ​​un gráfico (conectado). Si no me equivoco, se deduce del trabajo de Bodlaender [1, Teorema 3.11] que si el ancho de árbol de $G$ es aproximadamente de al menos $2k^3$ , entonces $G$ contiene una estrella $K_{1,k}$ como menor.

¿Podemos hacer que el término $2k^3$ más pequeño? Es decir, ¿decir que el ancho de árbol al menos $k$ ya implica la existencia de un $K_{1,k}$ menor? ¿Hay alguna prueba en alguna parte?

[1] Bodlaender, HL (1993). En pruebas de tiempo lineal menores con búsqueda de profundidad primero. Diario de Algoritmos, 14 (1), 1-23.

De hecho, es cierto que cada gráfico sin K 1 , k menor tiene un ancho de árbol como máximo k - 1 . Probamos esto a continuación, primero algunas definiciones:$G$$K_{1,k}$$k-1$

Deje sea el treewidth de G y ω ( G ) sea el tamaño máximo de un clique en G . Un gráfico H es una triangulación de G si G es un subgrafo de H y H es cordal (es decir, no tiene ciclos inducidos en al menos 4 vértices). Una triangulación H de G es una triangulación mínimo si no subgrafo adecuada de H es también una triangulación de G . Un subconjunto X de vértices de $tw(G)$$G$$\omega(G)$$G$$H$$G$$G$$H$$H$$4$$H$$G$$H$$G$$X$$G$$H$$G$$X$$H$H

La fórmula anterior implica que para demostrar que es suficiente para demostrar que todas las camarillas máximas potenciales de tienen un tamaño como máximo . Ahora demostramos esto. Sea una camarilla máxima potencial de y suponga que .G k X G | X | ≥ k + $tw(G) \leq k-1$$G$$k$$X$$G$$|X| \geq k+1$

Utilizaremos la siguiente caracterización de posibles camarillas máximas: un conjunto de vértices es una camarilla máxima potencial en si, y solo si, para cada par , de vértices no adyacentes (distintos) en hay un camino a partir de a en con todos sus vértices internos fuera de . Esta caracterización se puede encontrar en el documento Ancho de árbol y Relleno mínimo: Agrupando los separadores mínimos de Bouchitte y Todinca.G u v X P u , v u v G $X$$G$$u$$v$$X$$P_{u,v}$$u$$v$$G$$X$

Con esta caracterización es fácil derivar una menor de . Dejar que . Para cada vértice , ya sea es un borde de o hay un camino a partir de a con todos los vértices internos fuera . Para todos los que no son adyacentes a contraen todos los vértices internos de en . Terminamos con un menor de en el que es adyacente a todo , y X u ∈ X v ∈ X ∖ { u } u v G P u , v u v X v ∈ X u P u , v u G u X | X | ≥ k + 1 u $K_{1,k}$$X$$u \in X$$v \in X \setminus \{u\}$$uv$$G$$P_{u,v}$$u$$v$$X$$v \in X$$u$$P_{u,v}$$u$$G$$u$$X$$|X| \geq k+1$ . Entonces, el grado de en este menor es al menos , completando la prueba.$u$$k$