¿Se conserva el ancho de la camarilla debajo de las contracciones del borde?

13

Sea una clase de gráficos con ancho de camarilla acotado. En cada gráfico en se contraen algunos bordes (por ejemplo, al azar). ¿Ahora el ancho de la camarilla sigue limitado? $G$ $G$

En caso de que (en general) ya no esté acotado, estaría muy interesado en un contraejemplo.

graph-theory co.combinatorics cliquewidth Martin Lackner
fuente

16

$G$ $\{x,y\} \in E(G)$ $cw(G) < cw(G^{x,y})$ $G^{x,y}$ $G$ $\{x,y\}$

Mathieu Chapelle
fuente

¡Muchas gracias por tu respuesta! Esa es una referencia valiosa para mí. En caso de que nadie lo haya resuelto mientras tanto, mi pregunta está más o menos respondida :)

Martin Lackner

¿No es ese problema la dirección opuesta a la que se pregunta aquí?

Tsuyoshi Ito

Solo en el sentido de que esta pregunta pide un contraejemplo.

Martin Lackner

17

Este artículo reciente finalmente prueba que las contracciones de los bordes no preservan la propiedad de que un conjunto de gráficos ha limitado el ancho de la camarilla.

usuario13136
fuente

¿Se conserva el ancho de la camarilla debajo de las contracciones del borde?

Respuestas: