Estoy tratando de entender algunos conceptos sobre la descomposición modular y los gráficos de ancho de camarilla.
En este documento ("En gráficos P4-tidy"), hay una prueba de cómo resolver problemas de optimización como el número de camarilla o el número cromático usando la descomposición modular. Resolver estos problemas componiendo (usando suma disjunta o unión disjunta) dos gráficos G1, G2 es fácil cuando conoce la respuesta para G1 y G2. Dado que los gráficos principales en la descomposición de los gráficos P4-tidy son gráficos acotados (es decir, C5, P5, etc.), es fácil resolverlo para estos "casos base" y luego resolverlo para las composiciones. Por lo tanto, al usar el árbol de descomposición es posible resolver estos problemas en tiempo lineal.
Pero parece que esta técnica funcionaría con cualquier clase de gráfico, de modo que los primos de gráfico estén delimitados. Luego encontré este documento "Problemas de optimización de tiempo lineal solucionable en gráficos de ancho de camarilla acotada" que parece hacer la generalización que estaba buscando pero no podía entenderla muy bien.
Mi pregunta es:
1- ¿Es equivalente a decir que los primeros gráficos del árbol de descomposición están delimitados (como en el caso de los gráficos ordenados P4) y decir que un gráfico tiene la propiedad "Clique-Width" delimitada?
2- En caso de que la respuesta para 1 sea NO, entonces: ¿Existe algún resultado sobre clases de gráficos con primos de gráfico delimitados (como en gráficos P4-ordenados) y, por lo tanto, problemas de optimización como número de camarilla solucionable en tiempo lineal en todas estas clases? ?
fuente